Family 102Theoretical computer scienceLeanNot yet digestedfeatured
The Unique Games Conjecture and optimal approximation thresholds
Proves Khot's Unique Games Conjecture. Independent direct reductions also establish NP-hardness, on unweighted graphs, of approximation beyond the Goemans–Williamson ratio for Max-Cut, below factor two for Vertex Cover, and within any fixed constant factor for Min-UnCut and directed feedback vertex set. These direct proofs use established PCP and Label Cover hardness results.
Manuscripts in this family · 5
The Unique Games Theorem
Sep 23, 2026·paper.pdfLean
We prove the Unique Games Conjecture. For every fixed , we give a deterministic polynomial-time reduction from 3SAT to Unique Games over a fixed finite alphabet, with completeness at least and soundness at most δ.
A Direct Proof of Optimal Max-Cut Hardness
Sep 23, 2026·paper.pdfLean
We prove that approximating Max-Cut on simple unweighted graphs within any fixed factor greater than the Goemans–Williamson constant is NP-hard.
The Factor-Two Hardness Threshold for Vertex Cover
Sep 23, 2026·paper.pdfLean
We prove that minimum Vertex Cover is NP-hard to approximate within every fixed factor below two, even on simple unweighted graphs.
Constant-factor hardness of Min-UnCut
Sep 23, 2026·paper.pdf
For every fixed C > 1, approximating Min-UnCut within factor C is NP-hard, even on simple undirected unweighted graphs.
Constant-factor hardness of directed feedback vertex set
Sep 23, 2026·paper.pdf
Approximating minimum directed feedback vertex set within any fixed constant factor is NP-hard, even on unweighted digraphs.
OpenAI also released the model's reasoning trace for this result: reasoning trace (PDF).