Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > KILIAN RISSE:
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

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 >>>


TR21-021 | 18th February 2021
Per Austrin, Kilian Risse

Average-Case Perfect Matching Lower Bounds from Hardness of Tseitin Formulas

Revisions: 2

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 >>>


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

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 >>>




ISSN 1433-8092 | Imprint