The Unique Games Conjecture and optimal approximation thresholds

What OpenAI claims

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. (Lean)

Papers (5)

1. The Unique Games Theorem

   23 September 2026 · Preprint, not peer reviewed · PDF

   We prove the Unique Games Conjecture. For every fixed ε,δ ∈ (0,1/2), we give a deterministic polynomial-time reduction from 3SAT to Unique Games over a fixed finite alphabet, with completeness at least 1-ε and soundness at most δ.

2. A Direct Proof of Optimal Max-Cut Hardness

   23 September 2026 · Preprint, not peer reviewed · PDF

   We prove that approximating Max-Cut on simple unweighted graphs within any fixed factor greater than the Goemans–Williamson constant is NP-hard.

3. The Factor-Two Hardness Threshold for Vertex Cover

   23 September 2026 · Preprint, not peer reviewed · PDF

   We prove that minimum Vertex Cover is NP-hard to approximate within every fixed factor below two, even on simple unweighted graphs.

4. Constant-factor hardness of Min-UnCut

   23 September 2026 · Preprint, not peer reviewed · PDF

   For every fixed C > 1, approximating Min-UnCut within factor C is NP-hard, even on simple undirected unweighted graphs.

5. Constant-factor hardness of directed feedback vertex set

   23 September 2026 · Preprint, not peer reviewed · PDF

   Approximating minimum directed feedback vertex set within any fixed constant factor is NP-hard, even on unweighted digraphs.

Status

Preprint. The papers have not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.