Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR21-021 | 27th July 2022 17:20

Perfect Matching in Random Graphs is as Hard as Tseitin

RSS-Feed




Revision #2
Authors: Per Austrin, Kilian Risse
Accepted on: 27th July 2022 17:20
Downloads: 176
Keywords: 


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.



Changes to previous version:

This version addresses several issues pointed out by the journal referees.


Revision #1 to TR21-021 | 25th October 2021 16:58

Perfect Matching in Random Graphs is as Hard as Tseitin





Revision #1
Authors: Per Austrin, Kilian Risse
Accepted on: 25th October 2021 16:58
Downloads: 444
Keywords: 


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.



Changes to previous version:

Incorporated various reviewer comments which hopefully improved the exposition.


Paper:

TR21-021 | 18th February 2021 18:12

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


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.



ISSN 1433-8092 | Imprint