theoremnovel

The Unique Games Theorem

3SAT reduces to Unique Games with gap 1−ε1-\varepsilon vs δ\delta
main theorem; source of the hardness corollaries
Theorem·thm:ugc·§1.1 The theorem

Statement (paper)

For every fixed ε,δ∈(0,1/2)\varepsilon,\delta\in(0,1/2), there are an integer s≥1s\ge1 and a deterministic polynomial-time reduction from 3SAT\mathrm{3SAT} to explicit unweighted Unique Games instances GφG_\varphi over K=F2sK=\F_2^s such that φ satisfiable⟹val⁡(Gφ)≥1−ε,φ unsatisfiable⟹val⁡(Gφ)≤δ. \begin{aligned} \varphi\text{ satisfiable} &\quad\Longrightarrow\quad \val(G_\varphi)\ge1-\varepsilon,\\ \varphi\text{ unsatisfiable} &\quad\Longrightarrow\quad \val(G_\varphi)\le\delta. \end{aligned} The graph is simple and bipartite, and every constraint is a translation a(ve)=a(ue)+cea(v_e)=a(u_e)+c_e of KK. The alphabet, the degree of the running-time polynomial, and its constants depend only on ε,δ\varepsilon,\delta.

In plain English

For any fixed ε,δ∈(0,1/2)\varepsilon,\delta\in(0,1/2), 3SAT reduces in deterministic polynomial time to explicit unweighted, simple, bipartite Unique Games instances GφG_\varphi with translation constraints over K=F2sK=\F_2^s. Satisfiable formulas give value at least 1−ε1-\varepsilon, and unsatisfiable ones give value at most δ\delta.

Why it's here

This is the paper's main theorem. Its proof starts from the parity gap and its distinct-position preprocessing, builds the matrix game with latent gadget and shortcode decoding, removes weights by subdivision, and amplifies with parallel repetition. All parameters are fixed in an order that avoids circularity, so the alphabet and running-time constants depend only on ε,δ\varepsilon,\delta. The later corollaries on consequences of the Unique Games Theorem rest on this result.
Classified novel:
This is the paper's headline result: an NP-hardness proof of Khot's Unique Games Conjecture (Khot 2002), which until now had only partial progress such as the 2-to-2 Games Theorem. The new ingredients are the matrix game with a latent alphabet gadget and inverse-shortcode decoding, combined with subdivision and parallel repetition.

Uses

thmParallel repetition for projection gameslemLatent alphabet gadget with detecting noisethmInverse shortcode theorempropMatrix game completeness and soundness gaplemGood row advice is common and gives short answer setslemGood advice transfers to projected slicepropMatrix test passing yields decoding strategiesthmGap hardness for weighted parity equationslemPreprocessing to distinct variable positionslemSubdivision yields unweighted simple game

Used by

corGap hardness from a fixed SDP integrality gapcorOptimal hardness for ordering CSPscorConstant-factor hardness for cut and clustering problemslemUnique Games with constant left degree and strong satisfactionpropFinite ordering transfer from Unique GamesclaimFixed-instance verifier gap from strong-left UGclaimParameters fixed before invoking UG theoremclaimCopy normalization to unit incident weightclaimParameter choices give final ordering gap

Inside the proof

claimAlphabet-independent gap fixes repetition exponentclaimEffective choice of latent and shortcode parametersclaimChoosing the cube k and parity errorclaimYES and NO values of the final gameclaimOutput is simple bipartite translation gameclaimPolynomial-time explicit encoding

Figures

A two-column flow diagram. The left column, "The reduction", has three boxes linked by solid arrows: 3SAT to a weighted parity gap instance, then the latent matrix test (stable nonlinear map, Lemma 3.1), then via "Rounding and subdivision; parallel repetition" to unweighted simple bipartite Unique Games (Theorem 1.1). The right column, "Soundness on a NO input", has two branches with dashed arrows: assuming test acceptance at least 0.99 gives decoded advice strategies with agreement at least $\gamma>0$ (Proposition 5.3), while a NO parity instance gives agreement at most $\exp(-ck^{1/3})$ for every pair of strategies (Lemma 6.2). Both branches point to a bottom box stating a contradiction for sufficiently large $k$: $\exp(-ck^{1/3})<\gamma$.
Figure 1diagramp. 6
The solid arrows describe the reduction; the dashed arrows describe its soundness argument. The decoding lower bound follows from high test acceptance, while the clean-coordinate upper bound follows from the NO parity gap and applies to every advice strategy. The constants c,γ>0c,\gamma>0 are fixed before the tuple length kk grows.
What it shows
A two-column flow diagram. The left column, "The reduction", has three boxes linked by solid arrows: 3SAT to a weighted parity gap instance, then the latent matrix test (stable nonlinear map, Lemma 3.1), then via "Rounding and subdivision; parallel repetition" to unweighted simple bipartite Unique Games (Theorem 1.1). The right column, "Soundness on a NO input", has two branches with dashed arrows: assuming test acceptance at least 0.99 gives decoded advice strategies with agreement at least γ>0\gamma>0 (Proposition 5.3), while a NO parity instance gives agreement at most exp⁡(−ck1/3)\exp(-ck^{1/3}) for every pair of strategies (Lemma 6.2). Both branches point to a bottom box stating a contradiction for sufficiently large kk: exp⁡(−ck1/3)<γ\exp(-ck^{1/3})<\gamma.
Read from the image by claude-opus-5.5 · confidence 88%
SupportsthmThe Unique Games TheoremlemLatent alphabet gadget with detecting noisepropMatrix test passing yields decoding strategieslemAdvice agreement decays with clean coordinatesthmGap hardness for weighted parity equationsthmParallel repetition for projection gameslemSubdivision yields unweighted simple gamepropMatrix game completeness and soundness gap

Sources

PaperOpen
Section
§1.1 The theorem
Page
—
Label
thm:ugc
Line
sections/00-introduction.tex:22
Leannot aligned

Phase 2 aligns this node to a Lean declaration.