Perfect Matching in Random Graphs is as Hard as Tseitin
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 Po...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
TheoretiCS Foundation e.V.
2022-12-01
|
| Series: | TheoretiCS |
| Subjects: | |
| Online Access: | https://theoretics.episciences.org/9012/pdf |
| _version_ | 1797333214178574336 |
|---|---|
| author | Per Austrin Kilian Risse |
| author_facet | Per Austrin Kilian Risse |
| author_sort | Per Austrin |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-08T08:00:25Z |
| format | Article |
| id | doaj.art-35253e7d95504ac0bec3a7362c7737b9 |
| institution | Directory Open Access Journal |
| issn | 2751-4838 |
| language | English |
| last_indexed | 2024-03-08T08:00:25Z |
| publishDate | 2022-12-01 |
| publisher | TheoretiCS Foundation e.V. |
| record_format | Article |
| series | TheoretiCS |
| spelling | doaj.art-35253e7d95504ac0bec3a7362c7737b92024-02-02T12:31:07ZengTheoretiCS Foundation e.V.TheoretiCS2751-48382022-12-01Volume 110.46298/theoretics.22.29012Perfect Matching in Random Graphs is as Hard as TseitinPer AustrinKilian RisseWe 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.https://theoretics.episciences.org/9012/pdfcomputer science - computational complexityf.2.2f.1.3i.2.3f.4.1 |
| spellingShingle | Per Austrin Kilian Risse Perfect Matching in Random Graphs is as Hard as Tseitin TheoretiCS computer science - computational complexity f.2.2 f.1.3 i.2.3 f.4.1 |
| title | Perfect Matching in Random Graphs is as Hard as Tseitin |
| title_full | Perfect Matching in Random Graphs is as Hard as Tseitin |
| title_fullStr | Perfect Matching in Random Graphs is as Hard as Tseitin |
| title_full_unstemmed | Perfect Matching in Random Graphs is as Hard as Tseitin |
| title_short | Perfect Matching in Random Graphs is as Hard as Tseitin |
| title_sort | perfect matching in random graphs is as hard as tseitin |
| topic | computer science - computational complexity f.2.2 f.1.3 i.2.3 f.4.1 |
| url | https://theoretics.episciences.org/9012/pdf |
| work_keys_str_mv | AT peraustrin perfectmatchinginrandomgraphsisashardastseitin AT kilianrisse perfectmatchinginrandomgraphsisashardastseitin |