Kilian Risse

About

I am a postdoctoral researcher at LTH, Lund Univeristy hosted by Susanna de Rezende. Prior to this I was a postdoc at EPFL hosted by Ola Svensson and I have obtained my PhD from KTH Royal Institute of Technology in Sweden, under the joint supervision of Per Austrin, Johan Håstad, and Jakob Nordström.

My CV can be found here and you can rech me by email rissekil at gmail dot com.

Papers

• Supercritical Tradeoffs for Monotone Circuits, with Mika Göös, Gilbert Maystre and Dmitry Sokolov.
  STOC 2025. [Arxiv | ECCC]
• Clique Is Hard on Average for Unary Sherali-Adams, with Susanna de Rezende and Aaron Potechin.
  FOCS 2023. [Arxiv | talk | slides]
• Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz, with Jonas Conneryd, Susanna de Rezende, Jakob Nordström and Shuo Pang.
  FOCS 2023. [Arxiv | ECCC]
• Sum of Squares Lower Bounds for the Minimum Circuit Size Problem, with Per Austrin.
  CCC 2023. [Arxiv | ECCC]
• On bounded depth proofs for Tseitin formulas on the grid; revisited, with Johan Håstad.
  FOCS 2022. SICOMP. [Arxiv]
• Perfect Matching in Random Graphs is as Hard as Tseitin, with Per Austrin.
  SODA 2022. TheoretiCS. [Arxiv | ECCC]
• Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs, with Susanna de Rezende, Jakob Nordström and Dmitry Sokolov.
  CCC 2020. TheoretiCS. [Arxiv | ECCC]

Thesis

My full PhD thesis is available here and a shorter version without the appended papers can be obtained from DiVA.