\section{Introduction}\label{sec:introduction}

A permutation constraint prescribes exactly one label at one endpoint for
each label at the other. The Unique Games Conjecture asserts that systems
of such constraints can be hard to approximate even when almost all
constraints can be satisfied. We resolve this conjecture positively, with an
explicit unweighted reduction from \(\mathrm{3SAT}\).

\subsection{The theorem}

A \emph{Unique Games instance} has a finite vertex set, a finite alphabet
\(K\), and a nonempty list of oriented constraints
\(e=(u_e,v_e,\pi_e)\), where \(\pi_e\) is a permutation of \(K\).
A labeling \(a\) satisfies \(e\) when
\(a(v_e)=\pi_e(a(u_e))\). Its value is the fraction of satisfied
constraints, and \(\val(G)\) is the maximum value of a labeling.
The instance is \emph{explicit and unweighted} when the entire vertex
and constraint lists are written out, including the table of each
permutation. A simple bipartite instance has two disjoint vertex sets
and at most one constraint on each pair of opposite vertices.

\begin{theorem}[Unique Games Theorem]\label{thm:ugc}
For every fixed \(\varepsilon,\delta\in(0,1/2)\), there are an integer
\(s\ge1\) and a deterministic polynomial-time reduction from
\(\mathrm{3SAT}\) to explicit unweighted Unique Games instances
\(G_\varphi\) over \(K=\F_2^s\) such that
\[
\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(v_e)=a(u_e)+c_e\) of \(K\). The alphabet, the degree of the
running-time polynomial, and its constants depend only on
\(\varepsilon,\delta\).
\end{theorem}

Thus the result resolves the Unique Games Conjecture positively in its
usual edge-value formulation~\cite[Conjecture~2.5]{Khot10}.
The two errors are prescribed independently, before the alphabet is chosen.
Binary translation constraints are a known equivalent formulation of the
conjecture~\cite[Corollary~13 and Section~11.1]{KKMO07}; the reduction
here produces that form directly.

Theorem~\ref{thm:ugc} supplies the Unique Games hypothesis in earlier
hardness reductions for cut, covering, constraint-satisfaction, ordering,
deletion, and clustering problems
\cite{KKMO07,KhotRegev2008,Raghavendra08,GuruswamiEtAl2011OrderingCSP,CKKRS2006,DemaineEtAl2006Clustering}.
The reductions and the resulting approximation thresholds are due to
those authors. Section~\ref{sec:consequences} gives the precise problem
formulations, strict thresholds, and reduction qualifications, together
with proofs of the consequences.

\subsection{Proofs, codes, and the quantifiers}

The central difficulty is to retain completeness near one when every
label permits only one reply. The earlier connection between proof
verification and approximation hardness was developed by Feige,
Goldwasser, Lov\'asz, Safra, and Szegedy~\cite{FGLSS96}, by Arora and
Safra through proof composition~\cite{AroraSafra98}, and by Arora,
Lund, Motwani, Sudan, and Szegedy through the constant-query PCP
theorem~\cite{ALMSS98}. Bellare, Goldreich, and Sudan introduced the
long code and folding for verifier composition~\cite[Section~3.3]{BGS98}.
The long code of an answer \(a\) is the table \(f\mapsto f(a)\),
indexed by Boolean functions on the answer set. In H\aa stad's
parity-hardness proof, Fourier analysis recovers an outer-game strategy
from arbitrary proof tables that make his verifier accept sufficiently
often, without first recovering nearby codewords. His nearly satisfiable
parity gap is our starting hardness input~\cite{Hastad01}.

Khot introduced the Unique Games Conjecture in 2002 and gave an algorithm
based on semidefinite rounding~\cite{Khot02}.
Several algorithmic guarantees explain why its order of quantifiers
matters. For a fixed target error, Trevisan combines semidefinite rounding
with graph decomposition to obtain a polynomial-time
guarantee when the input error shrinks at the reciprocal-logarithmic
rate in the instance size~\cite{Trevisan08}. Charikar, Makarychev, and
Makarychev use randomized semidefinite rounding to obtain expected value
\(1-O(\sqrt{\epsilon\log q})\) from
a \(q\)-label instance of value at least \(1-\epsilon\)~\cite{CMM06};
this guarantee loses accuracy as the alphabet grows, whereas the
conjecture permits a large fixed alphabet after the errors are chosen.
Kolla's spectral enumeration gives a running-time bound in terms of the
dimension of a suitable spectral subspace of the label-extended graph,
whose vertices are variable--label pairs~\cite{Kolla11}. Arora, Barak, and Steurer use
spectral decomposition and enumeration to obtain near-satisfying
solutions for sufficiently small fixed completeness error, with a
guarantee independent of the fixed alphabet size~\cite{ABS10}; their
running-time bound is subexponential, not polynomial, for fixed positive
error. These are distinct limits on the known guarantees.

Integrality gaps concern the strength of a relaxation. Khot and Vishnoi
constructed Unique Games with semidefinite value arbitrarily close to
one and integral value arbitrarily close to zero, even with triangle
inequalities~\cite{KV15}. Barak, Gopalan, H\aa stad, Meka, Raghavendra,
and Steurer introduced the short code, based on Reed--Muller codes, as a
shorter substitute for the long code in applications including alphabet
reduction and quantitative integrality gaps~\cite{BGHMRS15}. These constructions constrain particular
relaxations; a hardness reduction requires a separate argument.
Bafna, Barak, Kothari, Schramm, and Steurer obtain polynomial-time
constant-value guarantees for nearly satisfiable translation games
whose graphs have suitable low-degree sum-of-squares hypercontractivity
certificates, including noisy hypercube and noisy Reed--Muller short-code
graphs~\cite{BBKSS21}. The rank-one matrix shortcode used below is a
different graph, and our argument does not assume these certificates.

\subsection{Grassmann expansion and the completeness obstacle}

The closest preceding hardness breakthrough concerns 2-to-1 and
2-to-2 games with imperfect completeness. A 2-to-1 constraint is a
projection with exactly two preimages per right label. A 2-to-2
constraint partitions the labels on each side into pairs and matches
these pairs bijectively, allowing the four combinations within a
matched pair. Khot, Minzer, and Safra's STOC~2017 work proposed a
Grassmann-graph reduction whose nonstandard soundness guarantee was
conditional on a structural hypothesis~\cite{KMS17}. Dinur, Khot,
Kindler, Minzer, and Safra's STOC~2018 work proposed a reduction with
ordinary edge-satisfaction soundness, conditional on an agreement
hypothesis~\cite{DKKMS25}; their expansion work formulated the relevant
structural problem and established partial cases~\cite{DKKMS21Expansion}.
Barak, Kothari, and Steurer connected expansion to the needed agreement
test through a binary matrix representation~\cite{BKS18}. The expansion
theorem of Khot, Minzer, and Safra completed this line in
2018~\cite{KMS23}.

These results established hardness for almost satisfiable 2-to-1 and
2-to-2 games and, as a consequence, a Unique Games gap with completeness
close to one half and arbitrarily small soundness. Obtaining Unique
Games completeness arbitrarily close to one was a separate problem.\footnote{A
separate companion proves hardness for exact 2-to-1 games with perfect
completeness and arbitrarily small fixed soundness, over fixed
alphabets~\cite[Theorem~1.1]{OpenAIPerfectTwoToOne2026}. It is not an input
to this proof.}

The degree-two matrix shortcode of Barak, Kothari, and
Steurer~\cite{BKS18} is the formulation used here: its vertices are
binary matrices and its steps add rank-one matrices. Their two-reply rule
permits either the old answer or its translate by the update's left factor;
requiring equality alone gives a one-half completeness guarantee. They
discussed higher-degree tests as a possible route to improving this
completeness~\cite[Section~1.6]{BKS18}. The inverse statement we use,
derived from Grassmann expansion, appears in Theorem~\ref{thm:shortcode}.
Ellis, Kindler, and Lifshitz later gave a shorter expansion proof using
hypercontractivity on spaces of linear maps~\cite{EKL26}; our external
input remains the Khot--Minzer--Safra theorem. Our proof keeps the
established degree-two inverse theorem and changes the noise using a
nonlinear map. The following comparison explains that choice.

\subsection{The construction and proof}

The uniform rank-one test illustrates the completeness problem. Let
\(M\) be a binary \(\ell\)-by-\(m\) matrix and fix a nonzero answer
\(z\in\F_2^m\). The evaluation function \(f_z(M)=Mz\) satisfies
\[
 f_z(M+a l^\top)-f_z(M)=a(l^\top z).
\]
For independent uniform \(a\in\F_2^\ell\) and \(l\in\F_2^m\), this
evaluation keeps its value with probability \((1+2^{-\ell})/2\), close
to one half. Our test changes the noise while retaining the ordinary
rank-one test as the structural tool for soundness.

For any prescribed \(p>0\), Lemma~\ref{lem:latent} fixes a rank threshold
and, for every sufficiently large \(\ell\), constructs a binary space
\(\mathcal V\) containing \(K=\F_2^\ell\), a map
\(C:\mathcal V\to K\), and a noise law \(\mu\) on \(\mathcal V\)
such that, for \(a\sim\mu\),
\[
 C(x+h)=C(x)+h\quad(h\in K),\qquad
 \Pr[C(x+a)\ne C(x)]\le p
\]
where \(x\) is uniform and independent of \(a\). At the same time, every
family of linear observations
whose restrictions to \(K\) have sufficiently large rank detects
\(a\) with probability at least \(1/8\). The rank threshold depends
only on \(p\) and is chosen before \(\ell\). The construction uses
quadratic blocks over a finite field: their nonlinear outputs become
increasingly stable under recursion, while a rank potential controls the
loss of linear observations. Section~\ref{sec:latent} proves this
separation and realizes the output translations as the subspace \(K\).

For the same nonzero \(z\), let \(P\in\Hom(\F_2^m,\mathcal V)\) be
uniform. The nonlinear evaluation \(P\mapsto C(Pz)\) compares the values
\[
 C(Pz)\quad\text{and}\quad C\bigl(Pz+a(l^\top z)\bigr)
\]
under the update \(P\mapsto P+a l^\top\). Here \(Pz\) is uniform in
\(\mathcal V\), independently of the latent noise \(a\), and
\(l^\top z\) is an independent fair bit. Its equality test therefore
fails with probability at most \(p/2\).

We start the reduction from binary parity equations on three distinct
variables. Each equation has four satisfying triples. A table on an equation
tuple \(U=(e_1,\ldots,e_k)\) is an affine map from the product of their
solution planes to \(\mathcal V\), represented by a matrix with
\(m=1+2k\) columns: one intercept column and two slope columns per
equation. Whenever one equation block affects a table only through one
actual bit, its reduced key records that variable and the entire induced
affine map. A projected table and its pullback receive the same key.
Grouping constant \(K\)-translates of keys into a vertex then folds the
answers: a label at the representative determines every translated
answer, and a shared key gives the same restored answer on both domains.
The resulting Unique Games test checks equality of the restored answers
on a table and its rank-one perturbation using the latent noise. A
near-satisfying global parity assignment gives the ideal evaluation above
on every tuple it satisfies, supplying near completeness. The key sharing
adapts Khot and Safra's virtual tables~\cite[Section~1.1]{KS13}, while the
translation orbits adapt the folding principle of Bellare, Goldreich,
and Sudan~\cite[Section~3.3]{BGS98}.

For soundness, suppose a labeling passes this test with probability at
least \(0.99\). A matrix frequency is a tuple
\(g=(g_i)_{i=0}^{m-1}\in(\mathcal V^*)^m\), one functional per column,
with character \((-1)^{\sum_i g_i(P\mathbf e_i)}\), where the
\(\mathbf e_i\) are the standard basis vectors of \(\F_2^m\). Averaging the phase increment of a
rank-one update over the uniform selector \(l\) gives
\[
\begin{aligned}
 \E_{a\sim\mu,l}(-1)^{\sum_i l_i g_i(a)}
   &=\Pr_{a\sim\mu}[g_i(a)=0\text{ for every }i],\\
 \E_{a\text{ uniform in }K,l}(-1)^{\sum_i l_i g_i(a)}
   &=2^{-\dim\Span\{g_i|_K\}}.
\end{aligned}
\]
The first multiplier is nonnegative and, by latent detection, is at most
\(7/8\) when the restriction rank is large. High acceptance therefore
forces a fixed amount of low-rank Fourier mass; the second multiplier
turns this into positive acceptance under the ordinary uniform rank-one
perturbation in \(K\). Using a linear complement
\(\mathcal V=K\oplus W\) fixed with the latent data, write the table as
\(P=(M,T)\), where \(M\) and \(T\) are its \(K\)- and \(W\)-valued
affine components, represented by matrices that include their constant
columns. The ordinary perturbation changes \(M\) and
fixes \(T\). Thus, for a positive fraction of pairs \((U,T)\), the
restored answer as a function of \(M\) often keeps its value under the
ordinary test. For the remaining soundness argument, take \(k\) to be a
sufficiently large integer cube, with the latent and shortcode parameters
fixed. On each such pair, the inverse shortcode theorem supplies
agreement with a target \(Mz+u\), for some \(z\in\F_2^m\) and \(u\in K\),
on a slice defined by at most a fixed number \(r_{\rm s}\) of row equations
and at most \(r_{\rm s}\) column equations.

For an independent uniform linear map \(A:K\to\F_2^{r_{\rm s}}\), the
visible advice about \((M,T)\) is \((A,T,AM)\). Together with \(U\), it
specifies \(T\) and the row fiber \(\{M':AM'=AM\}\) of \(K\)-valued affine
maps on the answer space of \(U\), including their constant terms. An erasure argument
proves that a fixed positive fraction of such data under unrestricted
table sampling on \(U\) admit additional column equations and a target
\(Mz+u\) certifying agreement on a nonempty slice. For each such datum
\((U,A,T,AM)\),
choose one certificate by a fixed rule depending only on that visible datum
and the fixed labeling. Folding then makes the certificate determine a short
nonempty set of valid answers on \(U\).

The advice experiment compares the equation tuple \(U\) with a question
\(O\) that independently replaces each equation by one uniformly chosen
variable with probability \(\beta\). Let \(\pi\) be the resulting
projection of actual answers. The referee samples a uniform table
\((M_O,T_O)\) on \(O\) and an independent map \(A\) with the law above.
On actual answer spaces,
it sends the visible data \((A,T_O\circ\pi,AM_O\circ\pi)\) with \(U\),
and \((A,T_O,AM_O)\) with \(O\). With the sparse choice of \(\beta\)
below, the full pulled-back table law, after averaging over projection
choices, is close to the unrestricted table law used for extraction.
On a positive fraction of joint samples the chosen \(U\)-certificate
transfers to a nonempty slice on \(O\) and retains agreement.

The two strategies are defined from their respective visible data. When its
advice admits a certificate, the \(U\)-strategy samples uniformly from its
short answer set; on other inputs it returns any valid answer. The \(O\)-strategy uses
a Fourier decoder on its own row fiber \(\{M':AM'=AM_O\}\). In the analysis,
the transferred certificate supplies
Fourier mass proving that this decoder reaches the projected \(U\)-answer
set with positive probability; the decoder itself does not receive that
certificate. The independent \(U\)-sample then gives full answer agreement
with probability at least a fixed \(\gamma>0\), independently of \(k\).
The sparse question comparison and Fourier decoding adapt the method of
Khot and Safra~\cite{KS13}; the correlated advice and use of vanishing
coordinates follow Khot, Minzer, and Safra~\cite[Sections~3.3--3.4]{KMS17},
with later use of that framework by Minzer and Zheng~\cite[Section~3]{MZ26}.

On a NO parity instance, every pair of advice strategies has agreement
tending to zero. The choice \(\beta=k^{-2/3}\) makes \(k\beta^2\to0\),
as needed for the table-law comparison, while \(k\beta\to\infty\) leaves
many singleton coordinates. A singleton is clean when every observed
row has zero coefficient on its retained bit. In the analysis, condition
on \(A\), the clean positions, the original advice intercept on \(O\),
and the sampled questions and advice slopes at the other positions. The
clean question pairs then retain the independent equation--variable law.
For each value of these fixed data, reconstructing each original local input
from its own clean questions defines strategies for the repeated outer game.
Parallel repetition bounds their success on the clean coordinates;
averaging over the number of those coordinates bounds the original advice
agreement by \(\exp(-c k^{1/3})\). This contradicts the decoded lower bound
for large \(k\).

For repetition we use the explicit projection-game bound of Dinur and
Steurer~\cite[Corollary~1.2]{DS14}. Raz established exponential decay
for general two-prover games~\cite{Raz98}, and Holenstein simplified the
proof~\cite{Holenstein2009}; those bounds depend on the answer alphabet.
Rao removed that dependence for projection games~\cite[Theorem~4]{Rao11}.
The Dinur--Steurer bound is applied first on the clean coordinates above
and finally after rounding the matrix-game weights and subdividing every
edge into four edges. Its alphabet independence permits the final
repetition exponent to be fixed before the latent alphabet, completing
the explicit unweighted reduction.

Figure~\ref{fig:overview} displays the reduction and the two incompatible
bounds that establish soundness.
\input{figures/overview}

Section~\ref{sec:preliminaries} fixes the game and probability conventions.
Section~\ref{sec:latent} constructs the gadget, and
Section~\ref{sec:game} defines the permutation test.
Sections~\ref{sec:matrix} and~\ref{sec:clean} give the two incompatible
bounds on the advice experiment. Section~\ref{sec:finish} completes
the parameter choices and the explicit Unique Games reduction.
Section~\ref{sec:consequences} then derives the approximation consequences
from the completed theorem and the cited reductions.
Appendix~\ref{app:finite-consequences} gives the simple strong-left
formulation and the finite ordering reduction used there.