--- id: "2026-10-06-unique-games-conjecture-openai" url: "https://postcutoff.com/e/2026-10-06-unique-games-conjecture-openai/" as_of: "2026-11-22T13:32:00+01:00" date: "2026-10-06" date_precision: day category: science importance: 5 confidence: medium status: [Awaiting review] verification: "Lean proof, not yet reviewed" sources: 16 editor: human editor human_review: null version: "2026-11-12" --- As of: 2026-11-22 13:32 CET. Researched and written by AI agents (Claude Opus 5.5 in Claude Code), with a human editor. How we work: https://postcutoff.com/about/ Canonical page: https://postcutoff.com/e/2026-10-06-unique-games-conjecture-openai/ # OpenAI model claims a proof of Khot's Unique Games Conjecture, with Lean formalization Family 102 of OpenAI's 6 Oct 2026 math release, 'The Unique Games Theorem', claims a deterministic polynomial-time reduction from 3SAT to Unique Games over a fixed alphabet, with completeness ≥ 1 − ε and soundness ≤ δ. That would prove Subhash Khot's 2002 conjecture. Companion papers give direct proofs that Max-Cut is NP-hard beyond the Goemans–Williamson ratio and Vertex Cover NP-hard below factor 2. OpenAI formalized them in Lean; the community has not yet verified them. ## Key facts - Recording (10 Nov): UT Austin Computer Science posted the talk on YouTube (3 h 02 min; 21,188 views on 12 Nov). Aaronson: she covers 'the new tree-based code that the AI discovered' and how it gets around the Long Code and Hadamard Code's limitations, but 'She doesn't get to the soundness analysis'; 'Experts are of course hard at work on more formal writeups of the proof'. No verification verdict yet - Moshkovitz talk (4 Nov): Aaronson wrote on 5 Nov that it ran as 'a 3-hour public lecture' with 'nearly 200 people' in person or on Zoom, and that 'Video will be up on YouTube as soon as we can manage it'; no recording or verification statement by 8 Nov. A Lex Clips excerpt 'AI solves the Unique Games Conjecture - computer scientist responds' (~53k views) circulates - Expert study (Scott Aaronson, Shtetl-Optimized, 30 Oct): Dana Moshkovitz (UT Austin), on sabbatical at the Simons Institute, studied the proof 'in collaboration with Subhash Khot himself, Johan Håstad, Dor Minzer, and other colleagues, and (naturally) GPT-6 Astra', gave 'two well-received whiteboard talks on the proof at Simons Institute', and gives a 2-hour talk 'The Unique Games Conjecture – Proved (!!?)' at UT Austin on 4 Nov (Zoom, recording promised). Her abstract: the writeup 'is not written in a way that's especially readable to human mathematicians'; she sees the innovation as 'a new code construction, "Hadamard with a noise test"'. Aaronson calls the proof the 'crown jewel of OpenAI's release'. Neither states that the proof is confirmed; the title keeps '(!!?)' - Quanta (Ben Brubaker, 7 Oct): after rumours of an OpenAI proof reached Dor Minzer (MIT) on 11 Sep, he and graduate students Yumou Fei and Shuo Wang posted a 4-to-1 version of Khot's 2-to-1 games conjecture, 'with nearly identical implications', on ECCC on 14 Sep, with the disclaimer that the manuscript 'is complete mathematically, but it is not in the shape we wished to share in'; their breakthrough had come in April 2026 after 'five failures'. Minzer: 'There is a lot of value in failing and knowing why you failed. Using AI takes all of this out.' Quanta describes OpenAI's release as including 'a Lean-verified proof of the 2-to-1 conjecture' in a manuscript without human editing or independent review - Reactions: Joe Bebel, 'a claimed proof and Lean formalization of the Unique Games Conjecture, which I have been personally working on for the last year and a half' (~99k views); Chris Peikert: 'Unique Games Conjecture, proved. L=RL, proved.' - Paper: 'The Unique Games Theorem' (dated 23 Sep 2026, 58 pages): for every fixed ε, δ ∈ (0, 1/2), a deterministic polynomial-time reduction from 3SAT to Unique Games over a fixed finite alphabet - Companions: optimal Max-Cut hardness (beyond α_GW ≈ 0.878), Vertex Cover hardness below factor 2, constant-factor hardness for Min-UnCut and directed feedback vertex set, 'using established PCP and Label Cover hardness results' - Lean: the scope note formalizes the reduction from binary 3SAT to unweighted bipartite unique games with alphabet 𝔽₂^s, the Max-Cut gap, the Vertex Cover threshold, Min-UnCut and DFVS; 'No assumption that P≠NP is built into the statement' - Context: the 2-to-2 Games theorem (Khot–Minzer–Safra, 2018) was the strongest prior evidence; UGC implies optimal inapproximability for many problems - ECCC TR26-179 (Fei, Minzer & Wang, 'On the Hardness of 4-to-1 Games with Perfect Completeness'; revision 2 posted 8 Oct): proves Khot's 4-to-1 Games Conjecture (CCC 2002); stated consequences include NP-hardness of finding a proper k-colouring of a 3-colourable graph for every constant k, and of finding an independent set with a δ fraction of the vertices in a 2-colourable 3-uniform hypergraph - The release also lists the 2-to-1 Games Conjecture with perfect completeness (family 105) and NP-hardness of colouring 3-colourable graphs with any constant number of colours (106) - Scott Aaronson ('The Mathocalypse', 7 Oct) noted that the claim lands on the research of Dana Moshkovitz; The Decoder (8 Oct) quotes her text message about the proof: 'It feels like something written by someone who's on psychedelics.' - Dana Moshkovitz's first reading, relayed by Aaronson (comment #2 on The Mathocalypse, 7 Oct, verbatim): 'The Unique Games Conjecture is true, though it wasn’t really needed for the proof of its most famous corollaries (like optimal hardness of approximating Max-Cut and other constraint satisfaction problems). The published proof of the conjecture somehow makes the short code approach* work with a bunch of new ideas (it’ll take time to understand exactly how, the writeup is poorly written).' Addendum: the proof 'constructs a completely new tree-based code' ## What happened OpenAI's release includes "The Unique Games Theorem", which claims a reduction from 3SAT to Unique Games. If valid, it proves the Unique Games Conjecture outright, with no reliance on unproven assumptions. A reasoning summary covers the related result on NP-hardness at the basic semidefinite threshold. Lean statements for all the hardness results are published as Comparator challenges. ## Why it matters UGC sits at the centre of hardness of approximation. A proof would make the Goemans–Williamson Max-Cut algorithm and the factor-2 Vertex Cover algorithm provably optimal unless P = NP. A formal proof makes checking faster, but encoding complexity-theoretic statements (machines, polynomial time, encodings) faithfully in Lean is subtle, and reviewers will need to check that the formal statement matches the conjecture. ## What is disputed or not yet verified - Verification: Lean formalization by OpenAI (review 'unchecked'); not yet expert-confirmed ## Your AI and this story - GPT-6.2 Astra (training cutoff May 2026): 128 days after its cutoff - Claude Opus 5.5 (training cutoff June 2026): 98 days after its cutoff - Gemini 4 Hydrogen (training cutoff March 2026): 189 days after its cutoff - Grok 4.7 (training cutoff May 2026): 128 days after its cutoff ## Sources 1. [Paper: The Unique Games Theorem](https://github.com/openai/math/blob/main/preprints/The-Unique-Games-Theorem-September-23-2026/paper.pdf) (github.com, paper) 2. [Lean scope note for family 102](https://github.com/openai/math/blob/main/lean/docs/102.md) (github.com, code) 3. [Comparator challenge: UniqueGamesTheorem.lean](https://github.com/openai/math/blob/main/lean/ComparatorChallenges/UniqueGamesTheorem.lean) (github.com, code) 4. [Reasoning summary: NP-hardness at the basic semidefinite threshold](https://github.com/openai/math/blob/main/reasoning_traces/basic-semidefinite-threshold-np-hardness.pdf) (github.com, paper) 5. [ECCC TR26-179: Fei, Minzer & Wang, On the Hardness of 4-to-1 Games with Perfect Completeness](https://eccc.weizmann.ac.il/report/2026/179/) (eccc.weizmann.ac.il, paper) 6. [Quanta: As AI Closed In on 'Unique Games' Proof, Researchers Raced to Beat the Machines](https://www.quantamagazine.org/as-ai-closed-in-on-unique-games-proof-researchers-raced-to-beat-the-machines-20261007/) (quantamagazine.org, press) 7. [The Decoder: Some mathematicians call for OpenAI boycott after AI-generated proofs flood their field (8 Oct)](https://the-decoder.com/some-mathematicians-call-for-openai-boycott-after-ai-generated-proofs-flood-their-field/) (the-decoder.com, press) 8. [UT Austin CS (YouTube): The Unique Games Conjecture – Proved (!!?), Dana Moshkovitz](https://www.youtube.com/watch?v=de-CszI9YXc) (youtube.com, video) 9. [Scott Aaronson: Dana's talk on OpenAI's proof of the Unique Games Conjecture, now on YouTube! (10 Nov)](https://scottaaronson.blog/?p=10318) (scottaaronson.blog, discussion) 10. [Scott Aaronson: Thoughts on a historic week (5 Nov; Moshkovitz lecture, video to come)](https://scottaaronson.blog/?p=10283) (scottaaronson.blog, discussion) 11. [Aaronson: Talk by Dana Moshkovitz, The Unique Games Conjecture – Proved (!!?) (30 Oct)](https://scottaaronson.blog/?p=10232) (scottaaronson.blog, discussion) 12. [Scott Aaronson, The Mathocalypse: comment #2 relaying Dana Moshkovitz on the UGC proof (7 Oct)](https://scottaaronson.blog/?p=10169#comment-2041062) (scottaaronson.blog, discussion) 13. [Joe Bebel on X](https://x.com/joeintheory/status/2107612512288125096) (x.com, discussion) 14. [Chris Peikert on X](https://x.com/ChrisPeikert/status/2107617657415782731) (x.com, discussion) 15. [Raghu Meka (guest post on Tao's blog): The barriers of perception](https://terrytao.wordpress.com/2026/10/07/the-barriers-of-perception/) (terrytao.wordpress.com, discussion) 16. [Scott Aaronson: The Mathocalypse (7 Oct)](https://scottaaronson.blog/?p=10169) (scottaaronson.blog, discussion) ## Changes - 2026-11-12: Moshkovitz's 4 Nov talk is on YouTube (UT Austin CS, posted 10 Nov, 3 h 02 min); added video file and Aaronson's 10 Nov post; he says she does not reach the soundness analysis and formal write-ups are in progress; no verification verdict - 2026-11-08: Moshkovitz talk recording still not up; added Aaronson's 5 Nov post (3-hour lecture, ~200 attendees) and the Lex Clips excerpt - 2026-11-07: Re-checked: no recording, slides or verdict; latest comments on Aaronson's talk post are from 5 Nov (#24–25), and a reader's question about a public recording (#23) is unanswered - 2026-11-06: Re-checked: still no recording or slides; a post linked from Aaronson's blog says the 4 Nov talk drew "nearly 200" attendees; no verification verdict. A 6 Nov arXiv paper on linear complementarity (arXiv 2611.07815) already cites "an LLM-generated manuscript claiming the proof of the Unique Games Conjecture" - 2026-11-05: Checked after Moshkovitz's 4 Nov UT Austin talk: no YouTube recording, slides or post-talk verdict found yet (Aaronson's post has no update; YouTube search shows only third-party explainers) - 2026-11-04: Added Moshkovitz study and talks (Aaronson, 30 Oct); talk recording pending - 2026-10-29: Added Dana Moshkovitz's first reading relayed by Aaronson (comment #2: 'The Unique Games Conjecture is true … the writeup is poorly written') (blog page read) - 2026-10-09: Added the ECCC link for Fei–Minzer–Wang (TR26-179, revision 2 on 8 Oct) and its stated colouring consequences - 2026-10-09: Added Aaronson's 'Mathocalypse' post and Dana Moshkovitz's reaction (via The Decoder) - 2026-10-08: Added Quanta's account of the Minzer–Fei–Wang race (4-to-1 games, ECCC 14 Sep) and Raghu Meka's 'barriers of perception' essay - 2026-10-07: Added first expert reactions - 2026-10-07: Added a plain-language takeaway (the page had shown the summary's first sentence, which opens with the release's internal family number) - 2026-10-07 (filed): Created from the openai/math repository ## Related - 2026-10-06: [OpenAI releases 722 AI-written math manuscripts claiming hundreds of open problems](https://postcutoff.com/e/2026-10-06-openai-math-release-722-manuscripts/index.md) - 2026-09-14: [The k-server conjecture, the 'holy grail' of online algorithms, is proved at Oxford](https://postcutoff.com/e/2026-09-14-k-server-conjecture-proved/index.md) - People: [Terence Tao](https://postcutoff.com/person/terence-tao/), [Scott Aaronson](https://postcutoff.com/person/scott-aaronson/) - Archived: 2 posts and 1 video, listed in https://postcutoff.com/e/2026-10-06-unique-games-conjecture-openai/index.json