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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

The Unique Games Theorem: A Short Self-Contained Proof

Ariel Elboim
1 citations
Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
preprint

The Unique Games Theorem: A Short Self-Contained Proof

Ariel Elboim
preprint en
1 citations

Abstract

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).

Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.