Proofmap
Papers
102 · The Unique Games Conjecture and optimal approximation thresholds
The Unique Games Theorem
Overview
Tree
Graph
Paper
Ask
Family 102
Theoretical computer science
Lean
58 pp · Sep 23, 2026
The Unique Games Theorem
What this paper proves
For a fixed
Λ
\Lambda
Λ
-instance
J
J
J
with
OPT
(
J
)
=
A
<
B
=
SDP
R
(
J
)
\operatorname{OPT}(J)=A<B=\operatorname{SDP}_R(J)
OPT
(
J
)
=
A
<
B
=
SDP
R
(
J
)
and any fixed
0
<
η
<
(
B
−
A
)
/
2
0<\eta<(B-A)/2
0
<
η
<
(
B
−
A
)
/2
, it is NP-hard to distinguish
Λ
\Lambda
Λ
-instances with
OPT
≥
B
−
η
\operatorname{OPT}\ge B-\eta
OPT
≥
B
−
η
from those with
OPT
≤
A
+
η
\operatorname{OPT}\le A+\eta
OPT
≤
A
+
η
. The key input is a deterministic polynomial-time reduction from 3SAT to Unique Games with translation constraints over
F
2
s
\mathbb{F}_2^s
F
2
s
and gap
1
−
ε
1-\varepsilon
1
−
ε
vs
δ
\delta
δ
, built on a latent alphabet gadget: a noisy equivariant coloring whose noise every high-rank test detects. This turns the Unique Games Conjecture into a theorem, so Raghavendra's integrality-gap hardness for every CSP holds unconditionally as NP-hardness.
Main theorem
corollary
routine
Gap hardness from a fixed SDP integrality gap
cor:raghavendra-consequence
If a fixed
Λ
\Lambda
Λ
-instance
J
J
J
has
OPT
(
J
)
=
A
<
B
=
SDP
R
(
J
)
\operatorname{OPT}(J)=A<B=\operatorname{SDP}_R(J)
OPT
(
J
)
=
A
<
B
=
SDP
R
(
J
)
, then for any fixed
0
<
η
<
(
B
−
A
)
/
2
0<\eta<(B-A)/2
0
<
η
<
(
B
−
A
)
/2
it is NP-hard to distinguish
Λ
\Lambda
Λ
-instances with
OPT
≥
B
−
η
\operatorname{OPT}\ge B-\eta
OPT
≥
B
−
η
from those with
OPT
≤
A
+
η
\operatorname{OPT}\le A+\eta
OPT
≤
A
+
η
.
Corollary 8.1 · as stated in the paper
Let
J
J
J
be a fixed
Λ
\Lambda
Λ
-instance with
A
=
OPT
(
J
)
<
B
=
SDP
R
(
J
)
A=\operatorname{OPT}(J)<B=\operatorname{SDP}_{R}(J)
A
=
OPT
(
J
)
<
B
=
SDP
R
(
J
)
. For every fixed
0
<
η
<
(
B
−
A
)
/
2
0<\eta<(B-A)/2
0
<
η
<
(
B
−
A
)
/2
, it is NP-hard to distinguish
Λ
\Lambda
Λ
-instances
I
I
I
satisfying
OPT
(
I
)
≥
B
−
η
from those satisfying
OPT
(
I
)
≤
A
+
η
.
\operatorname{OPT}(I)\ge B-\eta \qquad\text{from those satisfying}\qquad \operatorname{OPT}(I)\le A+\eta.
OPT
(
I
)
≥
B
−
η
from those satisfying
OPT
(
I
)
≤
A
+
η
.
Where the new idea lives · 4 novel steps
Theorem 1.1
The Unique Games Theorem
3SAT reduces to Unique Games with gap
1
−
ε
1-\varepsilon
1
−
ε
vs
δ
\delta
δ
Lemma 3.1
Latent alphabet gadget with detecting noise
Builds a noisy
K
K
K
-equivariant coloring whose noise is detected by high-rank tests
def
Generic binary subspaces of F^3
Defines generic subspaces of
F
3
F^3
F
3
: no proportional pairs, few aligned
z
z
z
Proposition 3.9
Full lifts detect the leaf symbol
Full lifts at depth
s
s
s
detect the leaf noise with probability ≥ 1/4
Shape of the proof
novel
other
Open the graph →
94
statements mapped
38
sections
4
novel steps
83
friction flags
Map
The proof as a tree and a dependency graph. Start at the top and click down.
Read the paper
The PDF with the map beside it; every statement is linked.
Ask
Questions answered with citations to the map you can click.