avatar

Kilian Risse

Postdoctoral Researcher
Lund University
rissekil@gmail.com


About

I am a postdoctoral researcher at LTH, Lund University hosted by Susanna de Rezende. Before that I spent some time at EPFL hosted by Ola Svensson. I completed my PhD at KTH Royal Institute of Technology in Sweden under the joint supervision of Per Austrin, Johan Håstad, and Jakob Nordström. I obtained my MSc and BSc from ETH Zürich.

News

Publications

  1. Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
    with Susanna de Rezende, David Engström and Yassine Ghannane
    Preprint, 2026
    Arxiv ECCC

  2. Supercritical Tradeoffs for Monotone Circuits
    with Mika Göös, Gilbert Maystre and Dmitry Sokolov
    57th Symposium on Theory of Computing (STOC), 2025
    Arxiv ECCC Conference Version

  3. Clique Is Hard on Average for Unary Sherali-Adams
    with Susanna de Rezende and Aaron Potechin
    64th Symposium on Foundations of Computer Science (FOCS), 2023
    Arxiv Video Conference Version

  4. Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
    with Jonas Conneryd, Susanna de Rezende, Jakob Nordström and Shuo Pang
    64th Symposium on Foundations of Computer Science (FOCS), 2023
    Arxiv ECCC Conference Version

  5. Sum of Squares Lower Bounds for the Minimum Circuit Size Problem
    with Per Austrin
    38th Computational Complexity Conference (CCC), 2023
    Accepted to Theory of Computing
    Arxiv ECCC Conference Version

  6. On bounded depth proofs for Tseitin formulas on the grid; revisited
    with Johan Håstad
    63rd Symposium on Foundations of Computer Science (FOCS), 2022
    SICOMP, 2025
    Arxiv Conference Version Journal Version

  7. Perfect Matching in Random Graphs is as Hard as Tseitin
    with Per Austrin
    Symposium on Discrete Algorithms (SODA), 2022
    TheoretiCS, 2022
    Arxiv ECCC Conference Version Journal Version

  8. 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
    35th Computational Complexity Conference (CCC), 2020
    TheoretiCS, 2025
    Arxiv ECCC Conference Version Journal Version

Service

Program Committee