{"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":2,"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"},{"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"}],"formalized":true,"family_title":"The Unique Games Conjecture and optimal approximation thresholds"}