oai-math-revised beta

Browse › Theoretical computer science › 102 The Unique Games Conjecture and optimal approximation thresholds

The Factor-Two Hardness Threshold for Vertex Cover

OpenAI · September 23, 2026

Lean

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 minimum Vertex Cover is NP-hard to approximate within every fixed factor below two, even on simple unweighted graphs.

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]
  • 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 the cover-density gap and its consequence for every fixed approximation factor below two, and links the corresponding Comparator challenge files. [family-level]

Digests and expositions

News and blogs

Elsewhere

Independent sites; their content is not reviewed here.

Cite

@misc{OAI:The-Factor-Two-Hardness-Threshold-for-Vertex-Cover-September-23-2026,
  author = {{OpenAI}},
  title = {{The Factor-Two Hardness Threshold for Vertex Cover}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/The-Factor-Two-Hardness-Threshold-for-Vertex-Cover-September-23-2026/paper.pdf}{OAI:The-Factor-Two-Hardness-Threshold-for-Vertex-Cover-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: