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

• Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
  with Susanna de Rezende, David Engström and Yassine Ghannane
  Manuscript. [Arxiv]
• 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.