Browse › Theoretical computer science › 102 The Unique Games Conjecture and optimal approximation thresholds
A Direct Proof of Optimal Max-Cut Hardness
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
We prove that approximating Max-Cut on simple unweighted graphs within any fixed factor greater than the Goemans–Williamson constant is NP-hard.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Comments and discussion
- Scott Aaronson, The Mathocalypse (Shtetl-Optimized, 2026-10-07). Relays Dana Moshkovitz's first reading of the release; her quoted messages note that it also contains "direct optimal NP hardness of approximation proofs" for the main applications of the UGC, bypassing the UGC. [family-level]
- Dana Moshkovitz (relayed by Scott Aaronson), comment #2 on The Mathocalypse (Shtetl-Optimized, 2026-10-07). Remarks that the UGC was not really needed for its most famous corollaries, naming optimal hardness of approximating Max-Cut as an example. [family-level]
- Comment thread, 102. The Unique Games Conjecture and optimal approximation thresholds (mahrud/openai-math-comments PR #102, opened 2026-10-09). Thread for human commentary on the five manuscripts; so far its only human comment points to the Fei–Minzer–Wang 4-to-1 games preprint and the Quanta article. [family-level]
Formalization
- OpenAI, Lean scope notes for family 102 (release Lean docs, lean/docs/102.md). Describes the formalized statements of all five results, for this paper a strictly separated Max-Cut gap above the Goemans–Williamson ratio on simple unweighted graphs, and links the corresponding Comparator challenge files. [family-level]
Digests and expositions
- Latent Seminar, Unique Games and optimal approximation thresholds (2026-10-07). Explains the direct proof's tree test, affine hashing and hidden-coordinate decoding, without claiming independent verification. [family-level]
News and blogs
- Agentic Economy, OpenAI's Unique Games claim: repairing the completeness gap (2026-10-08). Identifies the direct Max-Cut manuscript separately from the classical Unique-Games-based implication and says its reduction needs to be examined on its own. [family-level]
Elsewhere
- Emergent Mind: family 102
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:A-Direct-Proof-of-Optimal-Max-Cut-Hardness-September-23-2026,
author = {{OpenAI}},
title = {{A Direct Proof of Optimal Max-Cut Hardness}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/A-Direct-Proof-of-Optimal-Max-Cut-Hardness-September-23-2026/paper.pdf}{OAI:A-Direct-Proof-of-Optimal-Max-Cut-Hardness-September-23-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/102.md. The Lean statements have not been checked by people against the paper's claims.
Family 102: The Unique Games Conjecture and optimal approximation thresholds
Proves Khot's Unique Games Conjecture. Independent direct reductions also establish NP-hardness, on unweighted graphs, of approximation beyond the Goemans–Williamson ratio for Max-Cut, below factor two for Vertex Cover, and within any fixed constant factor for Min-UnCut and directed feedback vertex set. These direct proofs use established PCP and Label Cover hardness results.
Other papers in this family:
- The Unique Games Theorem · September 23, 2026
- The Factor-Two Hardness Threshold for Vertex Cover · September 23, 2026
- Constant-factor hardness of Min-UnCut · September 23, 2026
- Constant-factor hardness of directed feedback vertex set · September 23, 2026