Perfect matching in random graphs is as hard as Tseitin

DOI10.46298/theoretics.22.2zbMath1540.68162MaRDI QIDQ6562700

Kilian Risse, Per Austrin

Publication date: 27 June 2024

Published in: TheoretiCS (Search for Journal in Brave)

zbMATH Keywords

perfect matchingpolynomial calculusproof complexitysum of squarestopological embeddingbounded-depth Frege

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

This page was built for publication: Perfect matching in random graphs is as hard as Tseitin