All reports by Author Kilian Risse:

__
TR23-010
| 13th February 2023
__

Per Austrin, Kilian Risse#### Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem

__
TR21-021
| 18th February 2021
__

Per Austrin, Kilian Risse#### Average-Case Perfect Matching Lower Bounds from Hardness of Tseitin Formulas

Revisions: 2

__
TR19-174
| 2nd December 2019
__

Susanna de Rezende, Jakob NordstrÃ¶m, Kilian Risse, Dmitry Sokolov#### Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs

Per Austrin, Kilian Risse

We prove lower bounds for the Minimum Circuit Size Problem (MCSP) in the Sum-of-Squares (SoS) proof system. Our main result is that for every Boolean function $f: \{0,1\}^n \rightarrow \{0,1\}$, SoS requires degree $\Omega(s^{1-\epsilon})$ to prove that $f$ does not have circuits of size $s$ (for any $s > \text{poly}(n)$). ... more >>>

Per Austrin, Kilian Risse

We study the complexity of proving that a sparse random regular graph on an odd number of vertices does not have a perfect matching, and related problems involving each vertex being matched some pre-specified number of times. We show that this requires proofs of degree $\Omega(n/\log n)$ in the Polynomial ... more >>>

Susanna de Rezende, Jakob NordstrÃ¶m, Kilian Risse, Dmitry Sokolov

We show exponential lower bounds on resolution proof length for pigeonhole principle (PHP) formulas and perfect matching formulas over highly unbalanced, sparse expander graphs, thus answering the challenge to establish strong lower bounds in the regime between balanced constant-degree expanders as in [Ben-Sasson and Wigderson '01] and highly unbalanced, dense ... more >>>