Kilian Risse

According to our database, Kilian Risse authored at least 10 papers between 2020 and 2026.

Collaborative distances:

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

2026

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size.

Susanna F. de Rezende, David Engström, Yassine Ghannane, Kilian Risse

Electron. Colloquium Comput. Complex., 2026

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