Per Austrin ; Kilian Risse - Perfect Matching in Random Graphs is as Hard as Tseitin

theoretics:9012 - TheoretiCS, December 21, 2022, Volume 1 -
Perfect Matching in Random Graphs is as Hard as Tseitin

Authors: 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 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.

    Volume: Volume 1
    Published on: December 21, 2022
    Accepted on: August 3, 2022
    Submitted on: January 28, 2022
    Keywords: Computer Science - Computational Complexity,F.2.2,F.1.3,I.2.3,F.4.1

    Consultation statistics

    This page has been seen 326 times.
    This article's PDF has been downloaded 144 times.