ECCC-Report TR21-021https://eccc.weizmann.ac.il/report/2021/021Comments and Revisions published for TR21-021en-usSat, 20 Feb 2021 20:26:59 +0200
Paper TR21-021
| Average-Case Perfect Matching Lower Bounds from Hardness of Tseitin Formulas |
Kilian Risse,
Per Austrin
https://eccc.weizmann.ac.il/report/2021/021We 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.Sat, 20 Feb 2021 20:26:59 +0200https://eccc.weizmann.ac.il/report/2021/021