Kilian Risse
About
I am a
postdoc at LTH, Lund Univeristy hosted by Susanna de
Rezende. Prior to this I was a postdoc at EPFL hosted by Ola
Svensson while 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 you can reach by email rissekil at gmail dot com.
Papers
-
Supercritical Tradeoffs for Monotone Circuits, with
Mika Göös, Gilbert Maystre and Dmitry Sokolov.
To appear in 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. 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. TheoretiCS. [Arxiv | ECCC]
Thesis
My full PhD thesis is available here and a shorter version without the appended papers can be obtained from DiVA.