{"id":"openai-math/The-Unique-Games-Theorem","pdf":"https://github.com/openai/math/blob/main/preprints/The-Unique-Games-Theorem-September-23-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/The-Unique-Games-Theorem-September-23-2026","tags":["computational-complexity","unique-games","approximation-hardness"],"score":0,"title":"The Unique Games Theorem","domain":"Theoretical computer science","family":"102","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"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 δ .","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":6,"published":"2026-09-23","reactions":{},"discussion":[{"url":"https://gilkalai.wordpress.com/2026/10/07/updates-sharing-ai-progress-on-mathematics-amazing-and-my-lecture-plans/#:~:text=announces%20a%20proof%20of%20the%20Unique%20Games%20Conjecture","date":"2026-10-07","kind":"web","site":"Combinatorics and more","text":"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…","added":"2026-10-24","title":"Updates: Sharing AI progress on mathematics (amazing!); and my lecture plans","author":"Gil Kalai"},{"url":"https://scottaaronson.blog/?p=10169#:~:text=Or%20at%20least%2C%20we%E2%80%99re%20pretty%20sure%20that%20it%E2%80%99s%20a%20proof%21","date":"2026-10-07","kind":"web","site":"Shtetl-Optimized","text":"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…","added":"2026-10-24","title":"The Mathocalypse","author":"Scott Aaronson"},{"url":"https://www.quantamagazine.org/as-ai-closed-in-on-unique-games-proof-researchers-raced-to-beat-the-machines-20261007/","date":"2026-10-07","kind":"web","site":"Quanta Magazine","text":"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.","added":"2026-11-03","title":"As AI Closed In on ‘Unique Games’ Proof, Researchers Raced to Beat the Machines | Quanta Magazine","author":"Ben Brubaker"},{"url":"https://mathoverflow.net/a/515911","date":"2026-10-10","kind":"web","site":"mathoverflow.net","text":"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…","added":"2026-11-04","title":"Answer to: Which of the results released by OpenAI went against the conventional mathematical wisdom?","author":"Timothy Chow"},{"url":"https://x.com/thesasho/status/2109281180659163372","date":"2026-10-11","kind":"x","added":"2026-11-03","author":"Sasho Nikolov (thesasho@bsky.social)","handle":"thesasho"},{"url":"https://scottaaronson.blog/?p=10232#:~:text=I%20mentioned%20that%20my%20wife%20Dana","date":"2026-10-30","kind":"web","site":"Shtetl-Optimized","text":"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…","added":"2026-11-03","title":"Talk by Dana Moshkovitz: The Unique Games Conjecture – Proved (!!?)","author":"Scott Aaronson"}],"formalized":true,"family_title":"The Unique Games Conjecture and optimal approximation thresholds"}