Kilian Risse

According to our database, Kilian Risse authored at least 9 papers between 2020 and 2025.

Collaborative distances:

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

2025

Supercritical Tradeoffs for Monotone Circuits.

Mika Göös, Gilbert Maystre, Kilian Risse, Dmitry Sokolov

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

2024

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients.

Susanna F. de Rezende, Aaron Potechin, Kilian Risse

CoRR, 2024

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

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

Per Austrin, Kilian Risse

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Perfect Matching in Random Graphs is as Hard as Tseitin.

Per Austrin, Kilian Risse

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 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

2020

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

Proceedings of the 35th Computational Complexity Conference, 2020