Kilian Risse

22 papers A* 5A 2Journal 15
YearRankTypeTitle / Venue / Authors
2025 J jnl
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs.
TheoretiCS
Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov
2025 J jnl
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz.
CoRR
Jonas Conneryd, Susanna F. de Rezende, Jakob Nordström, Shuo Pang, Kilian Risse
2025 J jnl
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz.
Electron. Colloquium Comput. Complex.
Jonas Conneryd, Susanna F. de Rezende, Jakob Nordström, Shuo Pang, Kilian Risse
2025 J jnl
On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited.
SIAM J. Comput.
Johan Håstad, Kilian Risse
2025 A* conf
Supercritical Tradeoffs for Monotone Circuits.
STOC
Mika Göös, Gilbert Maystre, Kilian Risse, Dmitry Sokolov
2024 J jnl
Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients.
CoRR
Susanna F. de Rezende, Aaron Potechin, Kilian Risse
2024 J jnl
Supercritical Tradeoffs for Monotone Circuits.
CoRR
Mika Göös, Gilbert Maystre, Kilian Risse, Dmitry Sokolov
2024 J jnl
Supercritical Tradeoffs for Monotone Circuits.
Electron. Colloquium Comput. Complex.
Mika Göös, Gilbert Maystre, Kilian Risse, Dmitry Sokolov
2023 A* conf
Clique Is Hard on Average for Unary Sherali-Adams.
FOCS
Susanna F. de Rezende, Aaron Potechin, Kilian Risse
2023 A* conf
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz.
FOCS
Jonas Conneryd, Susanna F. de Rezende, Jakob Nordström, Shuo Pang, Kilian Risse
2023 A conf
Sum-Of-Squares Lower Bounds for the Minimum Circuit Size Problem.
CCC
Per Austrin, Kilian Risse
2023 J jnl
Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem.
CoRR
Per Austrin, Kilian Risse
2023 J jnl
Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem.
Electron. Colloquium Comput. Complex.
Per Austrin, Kilian Risse
2022 A* conf
On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited.
FOCS
Johan Håstad, Kilian Risse
2022 J jnl
On bounded depth proofs for Tseitin formulas on the grid; revisited.
CoRR
Johan Håstad, Kilian Risse
2022 A* conf
Perfect Matching in Random Graphs is as Hard as Tseitin.
SODA
Per Austrin, Kilian Risse
2022 J jnl
Perfect Matching in Random Graphs is as Hard as Tseitin.
CoRR
Per Austrin, Kilian Risse
2022 J jnl
Perfect Matching in Random Graphs is as Hard as Tseitin.
TheoretiCS
Per Austrin, Kilian Risse
2021 J jnl
Average-Case Perfect Matching Lower Bounds from Hardness of Tseitin Formulas.
Electron. Colloquium Comput. Complex.
Per Austrin, Kilian Risse
2020 A conf
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs.
CCC
Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov
2019 J jnl
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs.
CoRR
Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov
2019 J jnl
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs.
Electron. Colloquium Comput. Complex.
Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov