Kilian Risse


I am a postdoc at EPFL, hosted by Ola Svensson. Previously I obtained my PhD at 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 I can be reached by email at


  • 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. [conference version]
  • Sum of Squares Lower Bounds for the Minimum Circuit Size Problem, with Per Austrin.
    CCC 2023. [ECCC]
  • On bounded depth proofs for Tseitin formulas on the grid; revisited, with Johan Håstad.
    FOCS 2022. Invited to the special issue. [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. [Arxiv | ECCC]


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

Published by: Kilian Risse <kilian-dot-risse-at-epfl-dot-ch>
Updated 24/07/2023