Theoretical computer science·OpenAI Math·Result 102·Lean formalisation listed
The Unique Games Conjecture and optimal approximation thresholds
One of the 372 results in OpenAI's public mathematics catalogue, filed under theoretical computer science: 5 preprints, the latest dated 23 September 2026. This page quotes OpenAI's own summary of the claim, links the papers and abstracts, and embeds the animation.
Also known as Unique Games Conjecture; UGC
In one line: OpenAI reports a proof of the Unique Games Conjecture and optimal approximation thresholds (theoretical computer science) in 5 preprints, the latest dated 23 September 2026. It has not been peer reviewed. The channel's animation, Every OpenAI Math Result, Part 1 of 4: Goldfeld's Conjecture and 82 More, is on YouTube.
Chapter 68 of 83 in Every OpenAI Math Result, Part 1 of 4: Goldfeld's Conjecture and 82 More · starts at 23:15 · watch from there on YouTube →
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)
The Unique Games Theorem
OpenAI's abstract 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 δ.
A Direct Proof of Optimal Max-Cut Hardness
OpenAI's abstract 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
OpenAI's abstract 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
OpenAI's abstract 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
OpenAI's abstract 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.
Quick answers
- Is it proven?
- Not independently yet. OpenAI posted 5 preprints, the latest dated 23 September 2026; it has not been peer reviewed, so treat the result as OpenAI's claim until other mathematicians have checked it.
- What exactly does OpenAI claim?
- 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)
- Where is the proof?
- In the paper, The Unique Games Theorem (PDF).
- Is there a video?
- Yes, on YouTube (28:48, chapter 68).
Also in
The video
Every OpenAI Math Result, Part 1 of 4: Goldfeld's Conjecture and 82 More · Compilation · 28:48 · chapter 68 from 23:15 · description, sources and chapters →
Related results in Theoretical computer science
- 103Exact derandomization of logarithmic space: L=RL=BPLVideoLean
- 104Quasipolynomial algorithms for mean-payoff, stochastic and parity gamesLean
- 105Perfect completeness for 2-to-1 gamesVideoLean
- 106Hardness of coloring three-colorable graphsVideoLean
- 107Matrix multiplication with exponent at most 9/4VideoLean
- 108A cubic permanent–determinant lower boundVideoLean
