EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Perfect Matching in Random Graphs is as Hard as Tseitin

Per Austrin, Kilian Risse

TheoretiCS · 2022

DOI: 10.46298/theoretics.22.2 ↗

Kurz gefasst

Fachartikel in der Zeitschrift TheoretiCS, 2022. Verfasst von Per Austrin und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref). Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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\'asz-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.

Zitieren

APA

Austrin, P., & Risse, K. (2022). Perfect Matching in Random Graphs is as Hard as Tseitin. TheoretiCS. https://doi.org/10.46298/theoretics.22.2

Vancouver

Austrin P, Risse K. Perfect Matching in Random Graphs is as Hard as Tseitin. TheoretiCS. 2022. doi:10.46298/theoretics.22.2

BibTeX
@article{Austrin2022,
  author = {Austrin, Per and Risse, Kilian},
  title = {Perfect Matching in Random Graphs is as Hard as Tseitin},
  journal = {TheoretiCS},
  year = {2022},
  doi = {10.46298/theoretics.22.2}
}
Kostenlos starten →