Kilian Risse
About
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 firstname.lastname@epfl.ch.
Papers
-
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]
Thesis
My full PhD thesis is available here and a shorter version without the appended papers can be obtained from DiVA.