A Compressed Presentation of OpenAI's Proof of the Unique Games Theorem

We reconstruct the main argument of OpenAI's preprint "The Unique Games Theorem" (23 September 2026). Three earlier theorems are stated as inputs: Håstad's parity gap, the Khot–Minzer–Safra Grassmann expansion theorem, and Dinur–Steurer projection-game repetition. The remaining argument constructs stable nonlinear noise, extracts constant-output certificates, decodes them using only local information, and contradicts parallel repetition on clean coordinates. We retain the conditioning and parameter order on which these steps depend. The aim is a short, continuous proof for a reader comfortable with finite-field linear algebra and Fourier analysis on finite groups who has not read the preprint. We modify the root construction of the noise gadget, simplify certificate extraction, and rewrite the genericity proof; these changes are identified and proved explicitly, and are listed, with smaller ones, under Attribution. Status: an explanatory reconstruction prepared with Codex (OpenAI) and Claude (Anthropic). Its mathematical content received source-based reviews by AI agents; no human expert has reviewed it, and it does not certify the preprint. The files include the script and logs of our run of the Comparator check on OpenAI's Lean 4 formalization, which passed; that check concerns OpenAI's formal development, not this note (see Appendix A).

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-10-09
DOI
https://doi.org/10.5281/zenodo.23264901
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

A Compressed Presentation of OpenAI's Proof of the Unique Games Theorem

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

A Compressed Presentation of OpenAI's Proof of the Unique Games Theorem

Ariel Elboim
preprint en
1 citations

Abstract

We reconstruct the main argument of OpenAI's preprint "The Unique Games Theorem" (23 September 2026). Three earlier theorems are stated as inputs: Håstad's parity gap, the Khot–Minzer–Safra Grassmann expansion theorem, and Dinur–Steurer projection-game repetition. The remaining argument constructs stable nonlinear noise, extracts constant-output certificates, decodes them using only local information, and contradicts parallel repetition on clean coordinates. We retain the conditioning and parameter order on which these steps depend. The aim is a short, continuous proof for a reader comfortable with finite-field linear algebra and Fourier analysis on finite groups who has not read the preprint. We modify the root construction of the noise gadget, simplify certificate extraction, and rewrite the genericity proof; these changes are identified and proved explicitly, and are listed, with smaller ones, under Attribution. Status: an explanatory reconstruction prepared with Codex (OpenAI) and Claude (Anthropic). Its mathematical content received source-based reviews by AI agents; no human expert has reviewed it, and it does not certify the preprint. The files include the script and logs of our run of the Comparator check on OpenAI's Lean 4 formalization, which passed; that check concerns OpenAI's formal development, not this note (see Appendix A).

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.

A Compressed Presentation of OpenAI's Proof of the Unique Games Theorem — Ariel Elboim · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS