1 citations · 2 across the 9 of their papers we have counts for
8 papers · 1 filter
Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
Susanna F. de Rezende, David Engström, Yassine Ghannane +1
We prove superpolynomial length lower bounds for the semantic tree-like Frege refutation system with bounded line size. Concretely, for any function $n^{2-\varepsilon} \leq s(n) \l…
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
Jonas Conneryd, Susanna F. de Rezende, Jakob Nordström +2
We prove that polynomial calculus (and hence also Nullstellensatz) over any field requires linear degree to refute that sparse random regular graphs, as well as sparse Erdős-Rényi…
Supercritical Tradeoffs for Monotone Circuits
Mika Göös, Gilbert Maystre, Kilian Risse +1
We exhibit a monotone function computable by a monotone circuit of quasipolynomial size such that any monotone circuit of polynomial depth requires exponential size. This is the fi…
Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
Susanna F. de Rezende, Aaron Potechin, Kilian Risse
We prove that Sherali-Adams with polynomially bounded coefficients requires proofs of size to rule out the existence of an -clique in Erdős-Rényi random graphs…
Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem
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 \righta…
On bounded depth proofs for Tseitin formulas on the grid; revisited
Johan Håstad, Kilian Risse
We study Frege proofs using depth- Boolean formulas for the Tseitin contradiction on grids. We prove that if each line in the proof is of size then the number o…
Perfect Matching in Random Graphs is as Hard as Tseitin
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 bein…
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
Susanna F. de Rezende, Jakob Nordström, Kilian Risse +1
We show exponential lower bounds on resolution proof length for pigeonhole principle (PHP) formulas and perfect matching formulas over highly unbalanced, sparse expander graphs, th…