Kilian Risse

According to our database, Kilian Risse authored at least 7 papers between 2019 and 2023.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2023

Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem.

Per Austrin, Kilian Risse

Electron. Colloquium Comput. Complex., 2023

Clique Is Hard on Average for Unary Sherali-Adams.

Susanna F. de Rezende, Aaron Potechin, Kilian Risse

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz.

Jonas Conneryd, Susanna F. de Rezende, Jakob Nordström, Shuo Pang, Kilian Risse

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Perfect Matching in Random Graphs is as Hard as Tseitin.

Per Austrin, Kilian Risse

TheoretiCS, 2022

On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited.

Johan Håstad, Kilian Risse

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Average-Case Perfect Matching Lower Bounds from Hardness of Tseitin Formulas.

Per Austrin, Kilian Risse

Electron. Colloquium Comput. Complex., 2021

2019

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs.

Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov

Electron. Colloquium Comput. Complex., 2019