Perfect Matching in Random Graphs is as Hard as Tseitin

Abstract

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 Calculus (over fields of characteristic $\ne 2$) and Sum-of-Squares proof systems, and exponential size in the bounded-depth Frege proof system. This resolves a question by Razborov asking whether the Lovász-Schrijver proof system requires $n^{\delta }$ rounds to refute these formulas for some $\delta >0$. The results are obtained by a worst-case to average-case reduction of these formulas relying on a topological embedding theorem which may be of independent interest.

43 pages, 4 figures, SODA 2022

References in corpus (2)

• Sum-of-squares proofs and the quest toward optimal algorithms
• Quantum Advantage with Shallow Circuits Under Arbitrary Corruption