The Unique Games Theorem: A Short Self-Contained Proof
We give a short proof of the theorem of OpenAI's preprint "The Unique Games Theorem" (23 September 2026). It is self-contained apart from three earlier theorems, which are stated as inputs: Håstad's parity gap, the Khot–Minzer–Safra Grassmann expansion theorem, and Dinur–Steurer projection-game repetition. As in the source, the argument constructs stable nonlinear noise, extracts constant-output certificates, decodes them using only local information, and contradicts parallel repetition on clean coordinates. Relative to the source, several steps are simplified: the noise gadget's recursion is written in direct coordinates, and the survival of linear rank is proved by one induction on the height; genericity is proved by formal differentiation; test acceptance is bounded directly by the measure of good row fibers, without recoloring or concentration; the second player guesses a constant output and Fourier-samples one row; and a triangle of three equations replaces variable cloning. The companion note, included in this record, lists all departures from the source and their credits. A longer presentation that follows the source closely is doi:10.5281/zenodo.23264902. Status: a simplified reconstruction prepared with Codex (OpenAI), Claude (Anthropic) and other AI models, and checked step by step by separate AI reviewers. No human expert has reviewed it, and it does not certify the preprint. The Comparator check of OpenAI's Lean 4 formalization passed when we ran it; that check concerns OpenAI's formal development, not this paper (details in the companion note).
Authors
- Ariel Elboim (ORCID: https://orcid.org/0009-0001-1341-366X)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-10-09
- DOI
- https://doi.org/10.5281/zenodo.23265571
- Citations
- 1
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- preprint