Kilian Risse

Publication Activity (10 Years)

Years Active: 2019-2024
Publications (10 Years): 15

Top Topics

Average Case Complexity

Graph Colouring

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Susanna F. de Rezende, Aaron Potechin, Kilian Risse
Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients. CoRR (2024)
Per Austrin, Kilian Risse
Sum-Of-Squares Lower Bounds for the Minimum Circuit Size Problem. CCC (2023)
Susanna F. de Rezende, Aaron Potechin, Kilian Risse
Clique Is Hard on Average for Unary Sherali-Adams. FOCS (2023)
Jonas Conneryd, Susanna F. de Rezende, Jakob Nordström, Shuo Pang, Kilian Risse
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz. FOCS (2023)
Per Austrin, Kilian Risse
Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem. Electron. Colloquium Comput. Complex. (2023)
Per Austrin, Kilian Risse
Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem. CoRR (2023)
Per Austrin, Kilian Risse
Perfect Matching in Random Graphs is as Hard as Tseitin. SODA (2022)
Per Austrin, Kilian Risse
Perfect Matching in Random Graphs is as Hard as Tseitin. CoRR (2022)
Johan Håstad, Kilian Risse
On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited. FOCS (2022)
Johan Håstad, Kilian Risse
On bounded depth proofs for Tseitin formulas on the grid; revisited. CoRR (2022)
Per Austrin, Kilian Risse
Perfect Matching in Random Graphs is as Hard as Tseitin. TheoretiCS 1 (2022)
Per Austrin, Kilian Risse
Average-Case Perfect Matching Lower Bounds from Hardness of Tseitin Formulas. Electron. Colloquium Comput. Complex. 28 (2021)
Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs. Computational Complexity Conference (2020)
Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs. CoRR (2019)
Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs. Electron. Colloquium Comput. Complex. 26 (2019)