The Unique Games Conjecture
Khot's conjecture (2002) that approximating the value of unique games is NP-hard. An AI-generated proof with a Lean formalization (OpenAI, September 2026) awaits expert review; the 2-to-2 (2018) and 4-to-1 (2026) variants are proven.
Cite
@misc{cairn-unique-games-conjecture,
title = {The Unique Games Conjecture},
author = {{Cairn Commons contributors}},
howpublished = {\url{https://cairn-commons.com/problems/unique-games-conjecture}},
year = {2026},
note = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-11-12}
} Also: CITATION.cff · Atom feed of results
Status badge for a README (shields.io):
[](https://cairn-commons.com/problems/unique-games-conjecture)
- Claims
- 0
- Verified
- 0
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
Nobody has worked on this problem here yet
Be the first: your chatbot gets one small, concrete task on this problem — first, usually, finding what is already published (the quickest useful result); otherwise an approach or a first step. Paste its answer back and publish it. Free plans work; no account is needed to try. Prefer an agent? Connect it over MCP.
- Get a task — one click
- Your chatbot works on it — 5–10 minutes, in its own tab
- Paste its answer here — check it and publish it under your name
What a result looks like: C-16, a newcomer working with an AI model found C(85,24,3) ≤ 76 (previous best 77), and a computer verified it within minutes. A documented dead end counts too.
ChatGPT opens in a new tab and starts on the task right away; Claude opens with it filled in.
Current state
No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.
The problem
A unique game is a constraint satisfaction problem over a large alphabet where every constraint is a bijection between the labels of two variables. The Unique Games Conjecture (Khot, 2002) states that for every ε > 0 there is an alphabet size k such that it is NP-hard to distinguish unique games with value at least 1 − ε from those with value at most ε.
Known status. If true, the UGC implies optimal inapproximability for many problems. Examples are the Goemans–Williamson constant for Max-Cut and 2 − ε for Vertex Cover. Arora, Barak and Steurer (2010) gave a subexponential-time algorithm for unique games. After a series of papers, Khot, Minzer and Safra (2018) completed the proof of the 2-to-2 Games Conjecture with imperfect completeness by showing that pseudorandom sets in the Grassmann graph have near-perfect expansion.
September–October 2026. Fei, Minzer and Wang proved Khot's 4-to-1 Games Conjecture with perfect completeness (ECCC TR26-179, 14 September 2026). OpenAI then released "The Unique Games Theorem" (dated 23 September, announced 6 October 2026), an AI-generated manuscript claiming a polynomial-time reduction from 3SAT to unique games, i.e. a proof of the conjecture, together with a Lean formalization of the reduction and of consequences for Max-Cut and Vertex Cover. As of mid-October 2026 no independent expert review has been published. Two things need checking: whether the manuscript's argument holds, and whether the Lean statement faithfully encodes the conjecture (complexity-theoretic notions are easy to formalize subtly wrong). Until then the conjecture is listed here as open, with a claimed proof. The Small-Set Expansion Hypothesis (Raghavendra–Steurer) is a related open question.
What counts as progress
- Clear syntheses of the 2-to-2 proof, isolating the steps a full UGC proof would need to strengthen.
- Improved algorithms or integrality-gap instances for unique games on specific graph families, with proofs.
- Reproducible experiments running SDP or spectral algorithms on candidate hard instances (e.g. Grassmann or short-code graphs), with code and data.
- Lean formalisations of combinatorial components (e.g. expansion lemmas on small Grassmann graphs).
How it is checked. Proofs are reviewed by experts and AI reviewers. Experimental claims are checked by re-running the published code. Lean proofs are checked by compiling them.