The Unique Games Theorem
Source: github.com/openai/math/tree/main/preprints/The-Unique-Games…
We prove the Unique Games Conjecture. For every fixed $\varepsilon,\delta\in(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-\varepsilon$ and soundness at most δ .
Comments and reviews
No comments yet.
Discussed elsewhere
Or at least, we’re pretty sure that it’s a proof! There’s a Lean certificate , as there are for some of the other 372 breakthrough results (not all of them). But it also appears that no human has understood just about any of these proofs yet; the race to do so has just started. If you want an…
In the shadow of a rumored AI proof of one of the biggest problems in their field, three computer scientists rushed to publish their own milestone result.
From Scott Aaronson's blog : Positive solution to the Unitary Synthesis Problem, which Greg Kuperberg and I posed back in 2007. For every n-qubit unitary transformation U, there exists a classical oracle A such that U can be implemented in quantum polynomial time with access to A. This is the…
— Sasho Nikolov (thesasho@bsky.social) (@thesasho) Oct 11, 2026
I mentioned that my wife Dana—who’s been working on Subhash Khot’s Unique Games Conjecture since ~2009, for the entire time I’ve known her—has for the past few weeks (while on sabbatical at the Simons Institute in Berkeley) been spending essentially all of her time laboring to understand OpenAI’s…
API
curl /api/v1/records/openai-math/The-Unique-Games-Theorem
curl -X POST /api/v1/records/openai-math/The-Unique-Games-Theorem/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/The-Unique-Games-Theorem/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'
Updates: Sharing AI progress on mathematics (amazing!); and my lecture plansCombinatorics and moreGil KalaiOct 7, 2026
announces a proof of the Unique Games Conjecture and, separately, the 2-to-1 Games Conjecture with perfect completeness . Matrix multiplication. My post Cap Sets, Sunflowers, and Matrix Multiplication explored the connections between these problems. The new bound is over the complex numbers , a…