================================================================================ THE UNIQUE GAMES THEOREM A complete, friendly, and self-contained proof tour (improved v2: clearer, shorter, and with the quantifiers made explicit) ================================================================================ AUTHORS: OpenAI DATE: 2026-09-23 THIS FILE: The-Unique-Games-Theorem-v2.txt SOURCE PAPER: unique-games-theorem-original.txt ---------------- WHO IS THIS FOR? ---------------- This paper has one big idea, but its original form is a thicket of symbols. This version keeps every essential part of the proof while writing it in plain English and using ordinary examples wherever possible. A reader who knows: * mod-2 arithmetic (0+1=1, 1+1=0), * basic vectors and matrices, * the idea of "with high probability", * the idea that 3SAT is hard, can follow the whole argument. Nothing about Unique Games is assumed. The theorem we prove is: ================================================================================ THEOREM (Unique Games Theorem, edge-value form) ================================================================================ For every fixed pair of desired errors epsilon, delta in (0, 1/2), there is a finite alphabet K and a deterministic polynomial-time reduction from 3SAT to Unique Games with alphabet K such that: YES case: if the 3SAT formula is satisfiable, then value of the game is at least 1 - epsilon. NO case: if the 3SAT formula is unsatisfiable, then value of the game is at most delta. The game is simple and bipartite. Every constraint is a translation: label(right) = label(left) + constant. The alphabet K, the polynomial running time, and its constants depend only on epsilon and delta. ================================================================================ ================================================================================ PART 1. THE GAME, THE CONJECTURE, AND WHY THE ORDER OF QUANTIFIERS MATTERS ================================================================================ 1.1. What is a Unique Game? ------------------------------------------------------------ Imagine two friends are talking on a phone line. Each friend is asked a question. They must each answer with one color from a fixed palette of q colors: colors = {1, 2, 3, ..., q}. The possible question pairs are the edges of a graph. Each edge comes with a PERMUTATION of the q colors. A permutation is just a rule that takes the left friend's color and tells us the only acceptable color for the right friend. For example, with q=5, one edge might say: right answer = left answer + 1 (mod 5). So if the left friend says 3, the right friend must say 4. If the left friend says 4, the right friend must say 0. There is exactly one correct right answer for each left answer. That is the "unique" part. A translation is one very regular kind of permutation. The final game we construct uses only translations, which keeps the bookkeeping simple while still proving the strongest statement. The friends know the whole graph and all the permutation rules before the call. They may agree on any strategy they like. Then they are asked an edge, separated, and must answer using only their own question. The VALUE of the game is the largest possible fraction of edges that they can satisfy, over all strategies. A labeling is the simplest kind of strategy: assign one permanent color to every left vertex and one permanent color to every right vertex. It is a harmless mathematical fact that in these games both friends can be assumed to use a fixed labeling. The game value is: value(game) = max over all labelings of (satisfied edges) / (all edges). 1.2. The Unique Games Conjecture ------------------------------------------------------------ The Unique Games Conjecture, usually abbreviated UGC, says roughly: It is NP-hard to distinguish nearly satisfiable Unique Games from very unsatisfiable Unique Games. More precisely: for every epsilon, delta > 0 there is some fixed alphabet size q such that no polynomial-time algorithm can tell apart instances of value at least 1-epsilon from instances of value at most delta. That was a conjecture. This paper proves it. Our theorem actually gives the stronger, deterministic reduction form: a single algorithm that converts a 3SAT formula into an explicit game. The game is unweighted, simple, bipartite, and has translation constraints on a binary alphabet K = F_2^s. 1.3. Why the order of quantifiers is everything ------------------------------------------------------------ The conjecture would be false if epsilon, delta, and the alphabet size were ordered carelessly. Many algorithms solve Unique Games really well when epsilon is extremely tiny relative to the instance size. For example: * Trevisan's algorithm succeeds when the completeness error shrinks like 1/log(size of instance). * Charikar--Makarychev--Makarychev give a rounding algorithm with value 1 - O(sqrt(epsilon log q)). * Kolla's spectral enumeration works when a certain spectral dimension is small. * Arora--Barak--Steurer give a subexponential-time algorithm for a fixed small completeness error. None of these contradict the theorem, because the theorem lets us choose epsilon and delta FIRST, then fixes an alphabet K, and only then is the input allowed to grow. In particular, the alphabet does not grow with the input size. This paper proves that with that exact order of quantifiers, hardness wins. ================================================================================ PART 2. THE PROOF IN ONE PAGE ================================================================================ The proof has two halves. The forward half builds an object. The backward half proves that no cheap strategy can defeat it. FORWARD HALF (the reduction) ------------------------------------------------------------ 3SAT | | 1. Hastad's parity gap v Weighted 3-variable parity equations over F2: YES -> almost all satisfiable NO -> at most 1/2 + xi satisfiable | | 2. Make the three positions distinct v Parity equations with distinct variables: YES -> almost all satisfiable NO -> at most 4/5 satisfiable | | 3. Build tables on tuples of k equations | and apply a special LATENT ALPHABET GADGET v A weighted permutation-constraint game: YES -> value very close to 1 NO -> value at most 0.99 | | 4. Round weights, subdivide edges v An unweighted simple bipartite game: YES -> value close to 1 NO -> value at most 1 - 1/800 | | 5. Take the t-fold parallel product v Final Unique Games instance: YES -> value at least 1 - epsilon NO -> value at most delta BACKWARD HALF (soundness) ------------------------------------------------------------ We assume, for contradiction, that some labeling makes the matrix test pass with probability at least 0.99. Step A. Fourier comparison. High acceptance under the latent noise implies positive acceptance under the ordinary uniform rank-one test. Step B. Matrix decoding. The inverse shortcode theorem plus an erasure argument gives two local advice strategies that agree with constant probability gamma > 0. Step C. Clean coordinates. On a NO parity instance, every pair of advice strategies agrees with probability at most exp(-c k^(1/3)). For large enough k: exp(-c k^(1/3)) < gamma, which contradicts Steps B and C. Therefore no labeling passes the matrix test with probability 0.99. Hence the game value is at most 0.99 on the NO side. The two halves meet in Section 9. That is the complete argument. ================================================================================ PART 3. HASTAD'S PARITY GAP: THE HARD INPUT ================================================================================ Every hardness reduction starts with a problem we already know is hard. We use 3SAT. From it, Hastad's famous work produces a system of equations over F2, i.e. over the two numbers {0,1} with addition mod 2. Each equation involves three distinct positions of variables: x_a + x_b + x_c = b, where b is 0 or 1. A weighted parity instance is a finite list of such equations. Different occurrences have distinct IDs, even if two occurrences use the same variables. Each occurrence has a positive rational weight. All weights sum to one. The value of an assignment is the total weight of satisfied equations. The optimum is the largest possible value. THEOREM 3.1 (Weighted parity gap) ------------------------------------------------------------ For every fixed xi > 0, there is a deterministic polynomial-time reduction from 3SAT to weighted parity instances such that: YES case: optimum is at least 1 - xi. NO case: optimum is at most 1/2 + xi. This is our starting point. A satisfiable formula becomes a system where almost every equation can be satisfied. An unsatisfiable formula becomes a system where no assignment does much better than random. We then perform a small cleanup step. Some equations might use the same variable twice. That is inconvenient. We clone every variable one hundred times and replace the occurrence by a small weighted family of occurrences using clones. After this cleanup: LEMMA 3.2 (distinct positions) ------------------------------------------------------------ From a weighted parity instance we can construct, in polynomial time, another weighted parity instance in which the three variables of every equation are distinct, and: YES case: optimum is at least 1 - xi. NO case: optimum is at most 4/5. The exact upper-bound formula is optimum(E') <= (1 + optimum(E))/2 + 3/100. If optimum(E) <= 1/2 + xi and xi < 1/100, the right-hand side is at most 4/5. That is the only NO-side fact used in the rest of the proof. For the rest of the paper, "parity instance" means this cleaned-up instance with distinct positions. Its "ordinary equation-versus-variable game" chooses an equation and one of its three positions. The equation side answers with a satisfying triple; the variable side answers with a bit. If the optimum is at most 4/5, this ordinary game has value at most 14/15. This small constant gap will be amplified later by parallel repetition. ================================================================================ PART 4. THE LATENT ALPHABET GADGET ================================================================================ This is the new tool that makes completeness near one possible. 4.1. Why ordinary tests only give completeness near one half ------------------------------------------------------------ Imagine the game wants to ask about a large binary vector z. The most natural test is to add a random rank-one matrix: M -> M + a l^T, and check whether the answer stays the same. Here a and l are random binary vectors. If z is the intended answer, then: (M + a l^T) z = Mz + a (l^T z). But l^T z is a fair random bit. Therefore: Pr[l^T z = 0] = 1/2. So even the ideal honest answer satisfies the equality test only with probability about 1/2. That is not good enough for a Unique Games reduction. We need failure probability arbitrarily small. 4.2. The gadget ------------------------------------------------------------ We invent an alphabet V with a distinguished subspace K and a nonlinear map C : V -> K. The map is designed so that replacing x by C(x) is very forgiving to random noise. Think of C as a forgiving hash: a random small error usually leaves the answer unchanged, but a large enough family of independent linear tests still catches it. FORMAL LEMMA 4.1 (latent alphabet gadget) ------------------------------------------------------------ For every small p > 0 there is an integer r_* with the following property. For every sufficiently large ell, there exist: * a finite binary vector space V, * an identified subspace K = F_2^ell, * a map C : V -> K, * a rational noise distribution mu on V, such that: (1) TRANSLATION EQUIVARIANCE: For every x in V and every k in K, C(x + k) = C(x) + k. (2) SMALL CHANGE: For independent uniform x in V and noise a drawn from mu, Pr[ C(x + a) is not equal to C(x) ] <= p. (3) LINEAR DETECTION: For every linear subspace G of the dual space V* whose restriction to K has dimension at least r_*, Pr_{a ~ mu}[ some g in G has g(a) not 0 ] >= 1/8. In words: random noise usually does not move the nonlinear answer by much, but any sufficiently rich family of linear tests catches the noise with constant probability. Property (1) is why translations can be used as Unique Game constraints. Property (2) is why completeness can be nearly one. Property (3) is why cheating strategies still leave a detectable signal. 4.3. Where the gadget comes from ------------------------------------------------------------ The construction starts with a very small quadratic block. Over a big finite field F, define: Q(x1,x2,x3) = (x2 x3, x1 x3, x1 x2). The block answer is: C_blk(x,y) = y + Q(x). The vertical translations are y -> y + k, and they become output translations. The noise is chosen from special affine subspaces where the quadratic cross-terms cancel. One reason this works is the old friend from calculus and physics: quadratic interactions are tame under small symmetric perturbations. In the finite-field version: Q(x+a) + Q(x) + Q(a) is nonlinear but constrained to a hyperplane determined by the line containing a. 4.4. Why the rank stays detectable ------------------------------------------------------------ We need both small-change and detection simultaneously. The proof uses a harmonic potential: H_r = 1 + 1/2 + ... + 1/r. A generic family of linear observations loses at most one dimension when moving down the construction, and a uniformly chosen update loses dimension with probability proportional to 3 r / (number of lines). But the harmonic function turns that into an expected loss of only a constant per level. This is the heart of Lemma 4.1: a tailored random walk on ranks that decays slowly enough to survive until the leaf while the nonlinear change probability decays exponentially. 4.5. Quotient and enlargement ------------------------------------------------------------ Finally, two cosmetic but necessary steps: * We quotient out shifts that cause the same output translation, so the output translations are exactly the subspace K. * We enlarge the small output alphabet B to any larger K by using many random injections B -> K. This ensures the rank threshold r_* does not grow with ell. The result is exactly the gadget in Lemma 4.1. Every finite object can be found by a terminating deterministic search when p is rational, so the reduction is explicit. ================================================================================ PART 5. BUILDING THE OUTER MATRIX GAME ================================================================================ Now we make the actual Unique Games instance whose vertices are not variables but whole TABLES. 5.1. Tables ------------------------------------------------------------ Let U = (e_1, ..., e_k) be an ordered tuple of k parity equations. A table on U is an affine map from the satisfying answers of those equations to the latent space V. Each equation has four satisfying triples: (x,y, b_equation + x + y). So an equation answer is determined by its first two bits. Adding a homogeneous coordinate t_0 = 1 gives the answer space dimension m = 1 + 2k: one coordinate for the constant and two slopes per equation. A table P is represented by a matrix in Hom(F_2^m, V). In particular, P z means: evaluate the affine table at the valid answer z. 5.2. Two key identifications: keys and folding ------------------------------------------------------------ Different tables can secretly represent the same information. We first simplify each block. A slope pair (a_i,d_i) can: * have rank two, so the table truly depends on both equation bits; * have rank zero, so the block can be omitted; * have rank one, so the table depends only on one variable or one actual answer bit. The RETAINED coordinates form the support. The REDUCED table is the unique linear map on that support. The KEY of a table is its support plus its reduced table, including its intercept. A crucial compatibility: if a question O is obtained from U by projecting some equation blocks down to singleton variables, then a table on O and its pullback to U have the SAME KEY. Thus one vertex label can serve both questions consistently. Folding is then immediate. Adding a constant h in K to the intercept changes the key by h. We group each key with all of its K-translates into one vertex. A labeling of vertices defines, for any table P: F(P) = label(representative key) + c(P), where c(P) is the K-component of the key's intercept. This has the exact translation property: F(P + h e0^T) = F(P) + h. This is how the final Unique Game constraints become translations of the alphabet K. 5.3. The matrix test ------------------------------------------------------------ Sample: * U: k independent parity equations, * P: a uniform table on U, * a: latent noise drawn from mu, * l: a uniform bit vector of length m. Accept if: F(P) = F(P + a l^T). Here a l^T is rank one with the column a and row l. This test is a weighted permutation test on the orbit vertices. 5.4. Completeness ------------------------------------------------------------ Why does a near-satisfying parity assignment make this test pass with very high probability? Fix a global assignment satisfying the equations. On a tuple where all k equations are satisfied, the full answer z is actual and nonzero. The table's value becomes: C(P z) and after the update: C(P z + a (l^T z)). Since P z is uniform in V and independent of the noise a, the latent gadget says this changes with probability at most p. But equality only fails when l^T z = 1 AND the latent change is nonzero. Since l^T z is a fair bit independent of the rest, the failure probability is at most p/2. With probability at least 1 - k xi every equation in U is satisfied. Therefore completeness is: value >= 1 - k xi - p/2. Both k xi and p/2 can be made arbitrarily small. That is the entire point of the latent gadget. ================================================================================ PART 6. THE INVERSE SHORTCODE THEOREM ================================================================================ For soundness, we need a structural theorem. It says that any function which is too stable under uniform rank-one perturbations must be very simple on a small "window" of matrices. THEOREM 6.1 (equality soundness for degree-two shortcode) ------------------------------------------------------------ For every eta > 0 there are constants alpha > 0 and r_s >= 1 with the following property. If a function f : Mat(ell,m) -> F_2^ell satisfies Pr_{M,a,l}[ f(M) = f(M + a l^T) ] >= eta, then there is a nonempty row-and-column slice S, defined by at most r_s row equations and at most r_s column equations, such that for some vector z and some vector u, Pr_{M on slice S}[ f(M) = Mz + u ] >= alpha. A row-and-column slice is a set of matrices that all agree on some linear combinations of rows and columns. WHY THIS MATTERS ------------------------------------------------------------ The theorem says: if f almost always keeps its value when we add a tiny random rank-one matrix, then after zooming into a carefully chosen finite window, f looks exactly like the honest affine table M z + u. Thus a cheater who passes often must somewhere be behaving like a real table. The proof starts by identifying each matrix M with a subspace L_M inside F_2^ell + F_2^m: L_M = { (x, M^T x) : x in F_2^ell }. Then: dimension( L_M intersect L_N ) = ell - rank(M - N). So adding a nonzero rank-one matrix M - N exactly corresponds to taking a neighbor in the Grassmann graph of subspaces. A fiber that has retention at least eta under the matrix step becomes a set of Grassmann vertices with retention at least eta/4. The famous Khot--Minzer--Safra expansion theorem says that any set with constant retention has positive relative density inside a small interval of subspaces. Translating that interval back to matrices gives exactly a row-and-column slice and an affine target Mz + u. The constants alpha and r_s depend only on eta. No folding condition is needed. This theorem is the external structural engine of the proof. ================================================================================ PART 7. MATRIX EXTRACTION AND FOURIER DECODING ================================================================================ Now assume some labeling makes the matrix test pass with probability at least 0.99. We will use Fourier analysis to extract two highly agreeing local strategies for a related "advice experiment". 7.1. A change of noise ------------------------------------------------------------ For a table Q and a character sigma of K, define the sign: f_{Q,sigma}(P) = (-1)^{sigma(F_Q(P))}. A matrix Fourier frequency is a tuple g = (g_i) of linear functionals on V, one for each column i. The eigenvalue of g under the latent noise is: Lambda_g = Pr_{a ~ mu}[ g_i(a) = 0 for every i ]. This lies in [0,1]. The latent gadget's detection property says: if the restriction of the span of the g_i's to K has dimension at least r_*, then Lambda_g <= 7/8. For ordinary uniform rank-one noise with a uniform in K, the eigenvalue at g is instead: 2^(-dimension of span of restrictions of g_i to K). Therefore latent acceptance 0.99 forces at least 0.9 of the Fourier mass to sit on low-rank frequencies. Mass on low-rank frequencies gives positive acceptance under the ordinary uniform rank-one test. Concretely: LEMMA 7.1 (spectral comparison) ------------------------------------------------------------ If the table family passes the latent test with probability at least 0.99, then under ordinary uniform rank-one updates: E_{U,T} Pr_{M,a,l}[ F_U(M,T)=F_U(M+a l^T,T) ] >= 0.9 * 2^(-r_*). So a fixed positive fraction of fibers (U,T) have uniform rank-one acceptance at least some fixed multiple of 2^(-r_*). 7.2. From one slice to a useful row fiber ------------------------------------------------------------ The inverse shortcode theorem gives one good slice on each such (U,T). But the U-prover will not see all of M. It sees only the compressed rows S = AM, where A : K -> F_2^{r_s} is a random linear map. A technical erasure lemma proves that for a positive fraction of (U,T,A,AM), the row fiber { M : AM = S } contains a good slice. The proof is an averaging plus union bound argument using Hoeffding's inequality. It shows that if too many row fibers were bad, we could alter f by replacing the bad fibers with random noise and contradict Theorem 6.1. LEMMA 7.2 (good row advice) ------------------------------------------------------------ With probability at least g_0 > 0, the row advice (U,T,A,S) is good: there exist at most r_s column specifications and a target Mz + u, valid on the row fiber, that agrees with F on a nonempty set with probability at least alpha/2. The good set also determines a short nonempty answer set ANS of at most 2^{r_s} valid answers. Here "valid answer" means a vector whose homogeneous coordinate is 1. This last step uses folding in a clever way: if every vector in the naturally produced target coset had first bit zero, then translating by all h in ker A would make agreement only one per orbit, which is too small. So a valid representative must exist. 7.3. The projected advice experiment ------------------------------------------------------------ We now compare an equation-tuple question U with a sparse projection question O. Independently in each of the k blocks, with probability beta, we replace the whole equation by only one of its three variables. The projection pi maps full equation answers to projected answers. The two provers are given correlated advice: U-prover gets (U, A, T_O pi, S_O pi), O-prover gets (O, A, T_O, S_O). They must produce actual answers a_U and a_O with pi(a_U) = a_O. LEMMA 7.3 (padded table law) ------------------------------------------------------------ When beta = k^(-2/3), the distribution of the padded table pulled back from O to U tends in total variation to a uniformly random table on U as k grows along cubes. The distance is o(1). Therefore the good row advice extracted under unrestricted sampling remains present in the actual experiment. LEMMA 7.4 (transfer of a witness) ------------------------------------------------------------ For sufficiently large k, with probability at least gamma_1 > 0, the padded U-advice is good and the chosen witness transfers to O: a nonempty slice on O on which the projected target still agrees with F_O. The transferred answer set is the projection of the original short valid answer set. 7.4. The two decoders ------------------------------------------------------------ Now we define the strategies. U-prover: If its visible advice is good, it samples an answer uniformly from the short valid answer set ANS. If not good, it returns any valid answer. O-prover: It uses only its own row fiber { M : AM = S_O }. It chooses a representative M_0, writes the fiber as M_0 + X, and forms the sign function f_sigma on X. It samples a Fourier frequency Phi with probability proportional to |f_sigma_hat(Phi)|^2, then evaluates Phi on a fixed vector h chosen from ker A. If the sampled restriction sigma|_H is nontrivial, this produces a valid answer; otherwise it returns any valid answer. The O-prover does NOT see the U-prover's witness or answer set. The witness is used only in the analysis. LEMMA 7.5 (a transferred slice gives agreement) ------------------------------------------------------------ On data satisfying the transferred witness property, the two private rules agree with probability at least 2^(-ell r_s) (alpha/8)^2 2^(-r_s). Proof idea: the Fourier coefficients inside the transferred slice have total squared mass at least 2^(-ell r_s)(alpha/8)^2. When the O-prover samples such a frequency, its returned answer lies in the projected answer set. Independently, the U-prover hits a compatible representative with probability at least 2^(-r_s). Multiplying gamma_1 by this conditional agreement gives a constant gamma > 0. PROPOSITION 7.6 (matrix decoding) ------------------------------------------------------------ For every large cube k, any table family satisfying folding and sharing and passing the matrix test with probability at least 0.99 gives local strategies in the projected advice experiment with agreement at least a fixed constant gamma > 0. This is the first incompatible lower bound. ================================================================================ PART 8. CLEAN COORDINATES AND THE SOUNDNESS GAP ================================================================================ Now we prove the opposite bound: on a NO parity instance, no pair of advice strategies can agree often. 8.1. Parallel repetition ------------------------------------------------------------ We need one classical tool. THEOREM 8.1 (projection-game repetition, Dinur--Steurer) ------------------------------------------------------------ Let G be a finite projection game. Let G^t be the game with t independent copies, accepting only if all t copies accept. Then value(G) <= 1 - g => value(G^t) <= (1 - g^2/16)^t. The bound does not depend on the size of the question sets or answer alphabets. This alphabet-independence is essential: it lets us choose the repetition exponent before the final alphabet is chosen. 8.2. Clean coordinates ------------------------------------------------------------ Let D_O = (T_O, S_O) be the combined visible advice map from O to E_A = W + image(A). Conditional on the question O, every slope column and the intercept are independent uniform values of E_A. A coordinate i is CLEAN if the corresponding block was projected to a singleton and its one advice slope is zero. Conditional on the clean mask, the equation-variable pairs in the clean coordinates have exactly the ordinary equation-versus-variable law. The probability that a coordinate is clean is: p_A = beta * |E_A|^(-1). That is a positive constant depending only on the fixed dimensions. LEMMA 8.2 (clean-coordinate bound) ------------------------------------------------------------ If the original parity instance has optimum at most 4/5, then every pair of strategies in the advice experiment agrees with probability at most: ( 1 - beta * 2^(-dim W - r_s) / 3600 )^k <= exp( - 2^(-dim W - r_s) * k^(1/3) / 3600 ). PROOF IDEA ------------------------------------------------------------ Fix the advice map information outside the clean coordinates: A, the clean set, the intercept, and all slopes outside the clean set. For each clean coordinate i, offer the equation to one prover and the variable to the other. Each prover can reconstruct the entire advice input it originally received from this outside data plus its own clean questions. Why? The equation side sees the equation occurrence and can fill in the two zero slopes and the full intercept. The variable side sees the variable and can fill in the singleton slope and the original intercept. The outside data supplies all non-clean blocks. Therefore any agreement in the original advice experiment on every clean coordinate would also solve the t-fold product of the ordinary equation-versus-variable game. The ordinary game has value at most 14/15. Parallel repetition gives value at most (1 - 1/3600) per clean coordinate. Averaging over the clean mask and using the binomial moment bound proves the lemma. 8.3. The fixed matrix-game gap ------------------------------------------------------------ Choose beta = k^(-2/3). Then: k beta^2 = k^(-1/3) -> 0, needed for padded law comparison, k beta = k^(1/3) -> infinity, needed for many clean coords. For large k, the clean upper bound is smaller than gamma from decoding. This contradiction proves: PROPOSITION 8.3 (matrix game with adjustable completeness) ------------------------------------------------------------ For every large cube k and every parity instance: YES case: value(matrix game) >= 1 - k xi - p/2. NO case: value(matrix game) <= 0.99. The NO case uses 0.99 as the assumed acceptance threshold in Fourier decoding. The YES case uses the latent completeness lemma. This is the central tension. We now turn it into the final theorem. ================================================================================ PART 9. COMPLETING THE REDUCTION ================================================================================ The matrix game is still weighted and may have loops and parallel edges. We must turn it into the exact promised object. LEMMA 9.1 (rounding and subdivision) ------------------------------------------------------------ Let H be any finite permutation-constraint game with h positive rational occurrence weights summing to one. For any small tau > 0, there is an unweighted simple bipartite game B with 4Q edges, where Q = ceil(h/tau), and the same alphabet, such that: | value(B) - (1 - (1 - value(H))/4) | <= tau/4. Construction: round the weights to integer multiplicities. Replace each occurrence by a four-edge path with three fresh interior vertices. A satisfied occurrence extends to four satisfied edges; a violated one can satisfy only three. The interiors are disjoint, so exact equality holds after rounding. If the constraints of H are translations on a binary space, those of B are too. Translation by zero is the identity, and the inverse of a translation is still a translation. 9.1. Parameter order ------------------------------------------------------------ Fix desired errors epsilon, delta in (0,1/2). Choose positive rational epsilon_0 <= epsilon and delta_0 <= delta. 1. Choose a repetition exponent t such that (1 - 1/10240000)^t <= delta_0. This is possible because the post-subdivision NO gap is 1/800 and parallel repetition with gap g=1/800 gives g^2/16 = 1/10240000. 2. Choose p <= epsilon_0 / t, tau <= min(1/200, epsilon_0 / t). 3. From p, obtain the latent rank threshold r_*. Put eta = 2^(-r_*)/16. Obtain alpha and r_s from the inverse shortcode theorem. 4. Choose ell large enough, and construct the latent gadget with K = F_2^ell. This fixes V, C, mu, and the splitting V = K + W. 5. Choose a cube k large enough for: - shortcode theorem dimension thresholds; - the Hoeffding union bound; - the padded-law total variation bound; - the clean upper bound to be less than gamma. Enumerating cubes until all rational inequalities hold is a deterministic finite search whose cost depends only on epsilon and delta. 6. Finally choose xi small enough that k xi + p/2 <= epsilon_0 / t. This order is the entire proof of the quantifier claim. r_* is fixed before ell, ell before k, and k before xi. 9.2. The final theorem ------------------------------------------------------------ Given a 3SAT formula, apply Hastad's parity gap and make positions distinct. Build the matrix game from Section 5. For a satisfiable formula: value(H) >= 1 - d, d = k xi + p/2 <= epsilon_0 / t. For an unsatisfiable formula: value(H) <= 0.99. Apply rounding and subdivision: YES: value(B) >= 1 - (d + tau)/4. NO: value(B) <= 1 - 1/800. Finally take the t-fold parallel product G = B^t: YES: value(G) >= 1 - t(d+tau)/4 >= 1 - epsilon. NO: value(G) <= (1 - 1/10240000)^t <= delta. The output is unweighted, simple, bipartite, and has translation constraints on K^t = F_2^{ell t}. Thus s = ell t is the required fixed alphabet dimension. POLYNOMIAL ENCODING ------------------------------------------------------------ The parity instance size N gives N^k equation tuples. Because k is fixed after epsilon and delta, the number of matrix-test occurrences is polynomial in N. The number of tables, noise outcomes, and vectors per tuple is fixed. Each weight is a product of k parity weights and fixed rational factors. Keys and folded representatives are computed by linear algebra in fixed dimensions. Comparison of keys by pairs is polynomial. Rounding uses Q = O(h) copies, subdivision creates 3Q new vertices, and the final product has (4Q)^t edges. Permutation tables on F_2^{ell t} have constant size. Hence the entire reduction is explicit and deterministic polynomial-time. This completes the proof of the Unique Games Theorem. ================================================================================ PART 10. CONSEQUENCES ================================================================================ The theorem turns many conditional hardness results into unconditional NP-hardness results. The original reductions and thresholds are due to their cited authors; we state the resulting exact forms. 10.1. Max-Cut ------------------------------------------------------------ For the problem of splitting the vertices of a graph into two parts to maximize crossing edges, approximation above the Goemans--Williamson constant alpha_GW ~ 0.87856 is NP-hard at every fixed ratio in (alpha_GW, 1). The matching algorithm is due to Goemans and Williamson. The hardness reduction uses the Majority Is Stablest theorem. 10.2. Vertex Cover ------------------------------------------------------------ It is NP-hard to approximate Vertex Cover within factor 2 - epsilon for every fixed epsilon > 0. 10.3. Every CSP has an SDP threshold ------------------------------------------------------------ A constraint satisfaction problem over a fixed finite domain D with a fixed finite family of predicates Lambda has an explicit basic semidefinite program. For any fixed Lambda-instance J with A = OPT(J) < B = SDP(J), and every fixed gap eta > 0, it is NP-hard to separate instances of value at least B - eta from instances of value at most A + eta. Thus Raghavendra's SDP is exactly the optimal approximation algorithm for every fixed CSP. This statement needs a stronger promise form of Unique Games: the YES labeling satisfies all constraints incident to almost all left vertices. Section 11 derives that finite strong-left form. 10.4. Ordering CSPs ------------------------------------------------------------ Fix k >= 2 and a nonempty proper subset Pi of S_k. An ordering CSP asks for a global order on variables; an ordered k-tuple is satisfied if the order induced on it belongs to Pi. The random-ordering value is rho = |Pi|/k!. It is NP-hard to approximate the weighted finite ordering CSP above every ratio r > rho. The threshold is rho. Two famous examples: * Maximum Acyclic Subgraph: k=2, Pi={12}, so threshold 1/2. * Betweenness: k=3, Pi={123,321}, so threshold 2/6 = 1/3. 10.5. Cut, deletion, and clustering ------------------------------------------------------------ For every fixed constant C > 1, it is NP-hard to approximate within C: * Multicut, * Sparsest Cut (search version), * Min-2CNF^= Deletion, * Correlation Clustering in general weighted graphs. A companion paper proves uniform-demand Sparsest Cut hardness and a Gaussian propeller kernel-clustering threshold alpha_k = (8 pi / 9)(1 - 1/k). That companion result uses this theorem but is not an input to it. Under P not equal to NP, all of these problems have no deterministic polynomial-time constant-factor approximation. ================================================================================ PART 11. THE APPENDIX: FINITE STRONG-LEFT AND ORDERING TRANSFER ================================================================================ Some reductions need the Unique Games promise in a stronger, finite left-degree form. This appendix states those finite formulations and outlines their proofs. 11.1. Simple strong-left games ------------------------------------------------------------ THEOREM 11.1 (simple strong-left Unique Games) ------------------------------------------------------------ For every 0 < zeta, nu < 1 and integers d,H >= 1, there are integers h,R >= 1 with h >= H and d | h, and a deterministic polynomial-time reduction from 3SAT to explicit unweighted simple bipartite Unique Games instances with common left degree h, such that: YES case: a labeling strongly satisfies at least 1 - zeta of left vertices. Here "strongly satisfies" means every edge incident to that left vertex is satisfied. NO case: value < nu. The proof adapts the normalization and sequence construction of Khot and Regev. It makes the graph simple by retaining only sequences with all tags distinct. The strong-left completeness follows by lifting one labeling to all sequence vertices. Soundness follows because retained sequences have a constant fraction of all sequences, while the full sequence graph has small value. Polynomiality is explicit because all parameters depend only on zeta,nu,d,H. 11.2. Finite ordering transfer ------------------------------------------------------------ THEOREM 11.2 (finite ordering transfer) ------------------------------------------------------------ For every k >= 2, proper Pi subset S_k, and every delta > 0, there are integers q,H and positive rationals zeta,nu, depending only on k,Pi,delta, with the following property. For every R >= 1 and every simple strong-left Unique Games instance over [R] with left degree h >= H and q | h, there is a deterministic transformation producing an explicit list of weighted Pi-ordering constraints on distinct variables, with rational weights summing to one, such that: YES case: OPT_Pi >= 1 - delta, NO case: OPT_Pi <= rho_Pi + delta. The constants q,H,zeta,nu do not depend on R or h. The output variables are pairs (b,z) in B x [m]^R. The construction sorts local IDs into q blocks, averages over neighbors, and uses an invariance principle. It chooses all constants before applying the Unique Games theorem, exactly as required by the quantifier order. The appendix then makes the reduction expressed only with rational weights and finite enumerated neighbor choices, so the resulting ordering-CSP instance is explicit and polynomial. ================================================================================ PART 12. A SHORT DICTIONARY OF NOTATION ================================================================================ F_2 the field {0,1} with addition mod 2. [n] {1,2,...,n}. K final Unique Games alphabet, often F_2^ell or F_2^s. V latent alphabet containing K. C nonlinear map V -> K. mu rational noise distribution on V. value(G) maximum satisfied fraction of a game G. val(G) maximum satisfied fraction. OPT optimum value of an optimization instance. F_Q(P) restored answer determined by a labeling, question Q, and table P. Hom(E,F) linear maps from E to F. rank M dimension of the image of the linear map M. eps, delta desired completeness error and soundness error. xi parity-gap error, chosen small after k. k tuple length used in the outer game. beta k^(-2/3), sparse projection probability. r_* latent rank threshold. r_s maximum slice dimension in the shortcode theorem. alpha slice agreement lower bound. gamma decoded advice agreement lower bound. W a linear complement so V = K + W. A random linear map K -> F_2^{r_s}. S compressed matrix rows AM. T W-valued part of a table. M K-valued part of a table. pi answer projection U -> O. e_0^T homogeneous-coordinate functional. ================================================================================ PART 13. WHY THE PROOF IS COMPLETE ================================================================================ A common worry with famous results is that a sketch hides a crucial quantifier. This proof is designed so the quantifiers are visible. 1. Hastad's parity gap is external input. 2. The latent gadget is constructed effectively, and its rank threshold r_* is fixed before ell. 3. The inverse shortcode theorem is stated with exact dependencies and is translated from a known expansion theorem. 4. The Fourier comparison between latent and ordinary noise gives a positive surrogate acceptance. 5. The erasure lemma gives good row advice with positive probability and without assuming any property of the table family beyond folding, sharing, and acceptance. 6. The projected law comparison justifies using row advice from unrestricted tables inside the actual sparse experiment. 7. The two decoders are defined only from their own messages. 8. The clean-coordinate reconstruction is spelled out block by block, including intercept contributions. 9. Repetition is alphabet-independent, so its exponent is selected before the final alphabet is fixed. 10. All parameter choices are rational and ordered correctly. That is the complete proof. ================================================================================ KEY REFERENCES IN THE ORIGINAL PAPER ================================================================================ Khot 2002: On the Power of Unique 2-Prover 1-Round Games. Khot 2010: On the Unique Games Conjecture. Khot, Kindler, Mossel, O'Donnell 2007: Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs. Khot, Regev 2008: Vertex cover might be hard to approximate to within 2-epsilon. Raghavendra 2008 / thesis 2009: Optimal Algorithms and Inapproximability Results for Every CSP. Guruswami, Hastad, Manokaran, Raghavendra, Charikar 2011: Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant. Chawla, Krauthgamer, Kumar, Rabani, Sivakumar 2006: On the Hardness of Approximating Multicut and Sparsest-Cut. Demaine, Emanuel, Fiat, Immorlica 2006: Correlation Clustering in General Weighted Graphs. Hastad 2001: Some Optimal Inapproximability Results. Barak, Kothari, Steurer 2018/2019: Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. Khot, Minzer, Safra 2023: Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion. Dinur, Steurer 2014: Analytical Approach to Parallel Repetition. Khot, Safra 2013: A Two-Prover One-Round Game with Strong Soundness. Khot, Minzer, Safra 2017/2025: On Independent Sets, 2-to-2 Games and Grassmann Graphs. Minzer, Zheng 2026: Near Optimal Alphabet-Soundness Tradeoff PCPs. Mossel, O'Donnell, Oleszkiewicz 2010: Noise Stability of Functions with Low Influences. Isaksson, Mossel 2009: Maximally Stable Gaussian Partitions with Discrete Applications. Dinur, Khot, Kindler, Minzer, Safra 2021: On Non-Optimally Expanding Sets in Grassmann Graphs. Ellis, Kindler, Lifshitz 2026: An Analogue of Bonami's Lemma for Functions on Spaces of Linear Maps, and 2-2 Games. Bellare, Goldreich, Sudan 1998: Free Bits, PCPs, and Nonapproximability. Rao 2011: Parallel Repetition in Projection Games and a Concentration Bound. Raz 1998: A Parallel Repetition Theorem. Holenstein 2009: Parallel Repetition: Simplifications and the No-Signaling Case. Goemans, Williamson 1995: Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. Trevisan 2008: Approximation Algorithms for Unique Games. Charikar, Makarychev, Makarychev 2006: Near-Optimal Algorithms for Unique Games. Arora, Barak, Steurer 2010: Subexponential Algorithms for Unique Games and Related Problems. Kolla 2011: Spectral Algorithms for Unique Games. Khot, Vishnoi 2015: The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into l_1. Barak, Gopalan, Hastad, Meka, Raghavendra, Steurer 2015: Making the Long Code Shorter. Bafna, Barak, Kothari, Schramm, Steurer 2021: Playing Unique Games on Certified Small-Set Expanders. ================================================================================ END OF THE UNIQUE GAMES THEOREM (v2) ================================================================================