Unique Games and optimal approximation thresholds

Source and verification

This article explains family 102 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Approximation gaps and constraint games

An optimization problem asks for a feasible object whose value is as large or as small as possible. An $\alpha$-approximation for a maximization problem returns value at least $\alpha \mathrm{OPT}$, with $0<\alpha \le 1$. For minimization, a factor $A\ge 1$ means cost at most $A\mathrm{OPT}$. The algorithm must return a feasible object, not merely a numerical guess.

A hardness reduction transforms a satisfiability instance into an optimization instance with separated YES and NO ranges. For example, if YES instances have maximum value at least $c$ and NO instances have maximum value at most $s<c$, an approximation ratio greater than $s/c$ would distinguish them. Indeed, its output on a YES instance exceeds $s$, whereas no feasible output on a NO instance can do so. A deterministic polynomial-time approximation with that guarantee would therefore give a polynomial-time algorithm for the original satisfiability problem.

A Unique Games instance assigns a label $a(v)$ from one finite alphabet $K$ to each vertex. Every oriented edge $e=(u,v)$ specifies a permutation ${\pi }_e:K\to K$ and accepts precisely when

$$a(v)={\pi }_e(a(u)).$$

Its value is the maximum fraction of accepted constraints. A projection game allows an arbitrary map in place of a permutation. These are finite constraint systems; the “players” terminology encodes which local question each answer may depend on.

🏷️ The near-satisfiable Unique Games claim

Manuscript statement

For every fixed $\epsilon ,\delta \in (0,1/2)$, the principal manuscript constructs a deterministic polynomial-time reduction from 3SAT to explicit, unweighted, simple bipartite Unique Games with

$$\begin{array}{rl}\text{YES}:& \mathrm{val}(G)\ge 1-\epsilon ,\\ \text{NO}:& \mathrm{val}(G)\le \delta .\end{array}$$

The alphabet is $K=\{0,1{\}}^s$, and each constraint adds a fixed bit vector coordinatewise modulo two. The dimension $s$ and the running-time polynomial depend only on the two prescribed errors. (OpenAI, 2026)

The order is “choose the errors, then fix the alphabet, then process arbitrarily large inputs.” This does not assert one fixed alphabet that works for every soundness target. Nor does it assert perfectly satisfiable YES instances: $1-\epsilon$ is essential to the stated formulation.

The five manuscripts in this family share a hardness theme but develop separate arguments. The four optimization companions give direct routes to their gaps; they should not be read as four unchecked substitutions of the principal theorem into older reductions.

🏷️ Nonlinear stability and local decoding

For the analytic discussion, a function on binary strings has a Fourier expansion in the characters $(-1{)}^{{\sum }_{i\in S}{x}_i}$. The squared coefficients measure its Fourier mass, with their sum equal to its mean square. The influence of a coordinate of a Boolean function is the probability that flipping that coordinate changes its value. In the proofs below, large acceptance forces concentration of Fourier mass or a detectable influence, which must then be converted into a locally chosen source label.

The principal proof begins with a familiar obstruction. Let $M$ be a binary matrix and encode a nonzero answer $z$ by $f_z(M)=Mz$. A rank-one update gives

$$f_z(M+a{l}^{\mathsf{T}})-f_z(M)=a(l^{\mathsf{T}}z).$$

For uniform independent $a,l$, the scalar $l^{\mathsf{T}}z$ is a fair bit. Apart from the possibility $a=0$, the answer stays unchanged only half the time. Requiring one permitted reply thus loses the desired completeness near one.

The manuscript instead constructs a nonlinear map $C:\mathcal{V}\to K$ and a noise law $\mu$. For $h\in K$ and $a\sim \mu$, it requires both translation compatibility and stability:

$$\begin{array}{rl}C(x+h)& =C(x)+h,\\ \mathrm{Pr}[C(x+a)\ne C(x)]& \le p.\end{array}$$

Here $x$ is uniform and independent of $a$. At the same time, sufficiently many independent linear observations on $K$ detect the noise with probability at least $1/8$. Constructing these two properties together is a substantial input of the paper. For the nonlinear evaluation $P\mapsto C(Pz)$, a rank-one update changes the argument only when $l^{\mathsf{T}}z=1$, so the equality test fails with probability at most $p/2$.

For soundness, the test’s Fourier multiplier at observations $g_1,\dots ,g_m$ is

$$\underset{a\sim \mu }{\mathrm{Pr}}[g_i(a)=0\text{ for all }i].$$

It is nonnegative and at most $7/8$ at sufficiently high restriction rank. High acceptance therefore forces mass at low rank. Under uniform noise in $K$, the corresponding multiplier is $2^{-r}$, where $r$ is that rank. This transfers acceptance to an ordinary matrix test, whose inverse theorem produces agreement with a structured evaluation on a slice defined by boundedly many linear conditions.

Agreement on a slice still has to become a valid strategy for the source projection game. The source uses shared tables, short answer lists, and advice visible at each endpoint. A decoder at one endpoint cannot inspect the other endpoint’s question. Sparse replacement of equation questions by variable questions uses a parameter $\beta =k^{-2/3}$, giving the two different limits

$$\begin{array}{rl}k{\beta }^2& =k^{-1/3}⟶0,\\ k\beta & =k^{1/3}⟶\infty .\end{array}$$

The first pays for comparing sampling laws; the second leaves many useful coordinates for repetition. On coordinates where the advice vanishes, the original source questions remain independently distributed. Repetition makes their agreement exponentially small in $k^{1/3}$, contradicting the positive agreement extracted from the test. The paper then converts weighted constraints to explicit unweighted simple bipartite instances. This paragraph describes the proof architecture, rather than supplying the nonlinear construction or the inverse theorem.

🏷️ Max-Cut and its Gaussian benchmark

For a graph with nonnegative edge weights, Max-Cut maximizes the weight of edges whose endpoints receive different signs. Relax each sign to a unit vector $v_i$. An edge with $\rho =⟨v_i,v_j⟩$ contributes $(1-\rho )/2$ to the semidefinite objective. A uniformly oriented hyperplane separates those vectors with probability $\arccos (\rho )/\pi$: in their two-dimensional span, the separating directions occupy that fraction of angles.

Consequently the rounding guarantee is governed by

$$\begin{array}{rl}{\alpha }_{\mathrm{GW}}& =\underset{-1\le \rho <1}{\min }\frac{2\arccos \rho }{\pi (1-\rho )}\\ & \approx \mathrm{0.878567.}\end{array}$$

The direct Max-Cut manuscript claims ordinary NP-hardness for every fixed ratio strictly greater than ${\alpha }_{\mathrm{GW}}$, even on simple unweighted graphs. Its weighted gap, for fixed rational $t\in (0,1)$ and sufficiently small $\eta >0$, is

$$\begin{array}{rl}\text{YES}:& \mathrm{OPT}\ge (1+t)/2-\eta ,\\ \text{NO}:& \mathrm{OPT}\le (1+B(t))/2+\eta ,\\ B(t)& =\frac{2}{\pi }\arcsin t.\end{array}$$

Here edge weights sum to one, and the stated range is $\eta <(t-B(t))/4$. (OpenAI, 2026a) As $\eta \to 0$, the threshold ratio is $(1+B(t))/(1+t)$. Substituting $\rho =-t$ in the rounding expression gives exactly this ratio, explaining the same constant on both sides.

The direct proof uses a tree of Boolean tables. A Fourier monomial follows one child in each pair, while a second exploration follows both children of one selected pair. Their unique intersection at a chosen depth gives exactly one factor of the prescribed correlation $t$. Noise-stability analysis then detects an influential table entry. That entry is a gate input, not yet a source label. Affine hashing concentrates its Fourier mass, and a hidden coordinate makes the relevant context available using only each endpoint’s own question. The decoding loss must be independent of alphabet size, because the alphabet is chosen only after the required soundness.

🏷️ Vertex Cover and a factor-two gap

A vertex cover meets every edge; its complement is an independent set. The endpoints of a maximal matching form a cover of size $2|M|$, while every cover contains at least one endpoint of each of the disjoint matching edges. Thus this elementary algorithm has factor two.

The companion claims that for every fixed integer $m\ge 4$, one can reduce 3SAT to simple unweighted graphs with

$$\begin{array}{rl}\text{YES}:& \tau (G)<(1/2+1/m)n,\\ \text{NO}:& \tau (G)>(1-1/m)n.\end{array}$$

The ratio of thresholds is $2-6/(m+2)$, tending to two. Hence every fixed factor below two would distinguish a suitable gap. (OpenAI, 2026b)

The construction places grid-weight vectors on local question blocks. A norm is defined by taking the largest absolute sum over compatible local label selections. Vertices with vectors $S_v,S_w$ are adjacent when $\Vert S_v+S_w\Vert \le 2t$. A satisfying assignment defines one compatible linear functional; its upper tail gives an independent set of density nearly one half.

Conversely, a large independent set supplies an odd Lipschitz function with substantial variance. Restricting to a small batch of positions must preserve variance after conditioning only on each position’s own question. Gradients of those conditional means yield short label lists. A joint gradient has compatibility information; conditional Jensen transfers list mass back to that joint object before compatibility is used. This order matters: separately conditioned gradients need not themselves form a compatible selection. The manuscript obtains an expected number of simultaneously hit lists at least two, whereas source-game soundness bounds it below $3/2$.

🏷️ Min-UnCut and the cost of small residuals

Min-UnCut minimizes the number of edges lying inside the two parts. Equivalently, it is the minimum number of edges whose deletion makes the graph bipartite. If $m=|E|$, then its optimum is $m-\mathrm{MaxCut}(G)$.

This identity does not transfer multiplicative ratios. On a graph with optimum uncut cost $k\ll m$, an $\alpha$-approximation for Max-Cut only bounds the returned uncut cost by

$$m-\alpha (m-k)=(1-\alpha )m+\alpha k.$$

The term proportional to $m$ can swamp $k$.

For every fixed integer $K\ge 2$, the Min-UnCut companion claims a deterministic reduction to $(G,k)$, with $k\ge 1$, such that YES cost is at most $k$ and NO cost is strictly greater than $Kk$. (OpenAI, 2026b) The positive threshold avoids confusing this claim with bipartiteness testing, which decides whether the optimum is zero.

The proof first builds weighted comparisons between bits. Gaussian smoothing, Fourier extraction, and locally visible advice convert low comparison cost into a source-game labeling. A large odd Fourier coefficient of a function on affine queries identifies an actual label; the coefficient bound is independent of the alphabet. Finite rational approximation of the joint query law then gives an explicit comparison system.

To realize it as a graph, an equality demand uses a path of length four and an inequality demand uses a path of length three, with fresh internal vertices. Along a completely cut path the endpoint signs agree exactly when its length is even. If the demanded parity fails, one uncut edge suffices and at least one is necessary. Thus each path contributes exactly the violated demand’s cost, with no additive baseline. Preserving absolute cost is what preserves a large multiplicative gap.

🏷️ Directed feedback deletion and one common budget

A directed feedback vertex set meets every directed cycle, or equivalently leaves an acyclic induced graph after deletion. The fifth manuscript claims hardness within every fixed factor $A\ge 1$ on unweighted digraphs: YES instances have optimum at most a positive threshold $k$, and NO instances have optimum greater than $Ak$. (OpenAI, 2026b) This is an unbounded sequence of fixed-factor obstructions; it does not specify a growing lower-bound rate as a function of graph size.

The source starts from imperfect-completeness two-to-one games. Protected vertices encode ranks, while deletable test vertices enforce comparisons. Any inexpensive feedback set leaves a topological order. Rank spreading and shared prefixes turn that order into a distribution of monotone Boolean functions on subsets of labels, chosen before a fresh source constraint is drawn.

For a function $f$, the proof introduces a pivotality budget $B(f)$: sum over labels the probability that the label is pivotal at some prefix of a random permutation of the others. This quantity controls influence at every bias, with bounded expectation. A junta theorem approximates each function using a bounded list of relevant labels. The list-size bounds are fixed before the alphabet.

At many dyadic biases, low source-game value makes the endpoint lists typically use disjoint projection fibers. A coupling then forces a positive contribution to a tail-sum estimate for $B(f)$. All contributions concern the same random variable under the same distribution, so adding sufficiently many contradicts its expected budget. Separate influence bounds for unrelated functions at each bias would not permit this addition. Finally the manuscript removes rational vertex costs by explicit duplication.

🏷️ Key steps and proof outlines

Spectral mass as a quantitative decoding resource

The proof in “Comparing the two matrix perturbations” makes the transfer to an ordinary matrix test explicit. Write $B$ for the total squared Fourier mass, averaged over questions and output characters, on frequencies of restriction rank at least $r_{\ast }$. Parseval gives total mass one. The latent test has multiplier at most $7/8$ on that part and at most one elsewhere. Consequently acceptance at least $0.99$ implies

$$0.99\le (1-B)+\frac{7}{8}B,B\le \mathrm{0.08.}$$

Under the uniform matrix perturbation, a rank-$r$ frequency has multiplier $2^{-r}$. The mass below $r_{\ast }$ therefore contributes at least $0.92^{-r_{\ast }}$ to the new acceptance. This is the precise input to the inverse theorem: one does not try to infer a label directly from the original high acceptance. (OpenAI, 2026e)

The slice extraction interface

Positive equality acceptance supplies positive density on a slice cut out by boundedly many row and column equations. The density and number of equations depend on the acceptance threshold, not on the number of source questions.

To understand its proof, associate a matrix $M$ with the graph of its transpose, $L_M=\{(x,M^{\mathsf{T}}x)\}$. Then

$$\dim (L_M\cap L_N)=\ell -\mathrm{rank}(M-N).$$

A rank-one matrix step is thus adjacency of subspaces in a matrix chart. The source applies the cited Grassmann expansion theorem to a retained fiber of the response function. An interval of subspaces containing one fixed subspace and lying inside another becomes precisely a bounded collection of row and column equations. This explains geometrically why the output is a slice, rather than agreement on the entire matrix space.

The next erasure argument is also essential. Suppose useful row fibers occupied too little mass. Randomly replace all their table entries. Acceptance changes by at most twice the replaced mass, since each endpoint is uniform. On the other hand, a concentration bound and a union bound over slice descriptions make accidental agreement on every replaced slice small. The inverse theorem would demand a new dense slice; that slice would already have been useful and hence erased. This contradiction produces many useful fibers, allowing locally observed row advice to find one with positive probability.

Why the four companions require separate soundness arguments

In Max-Cut, the analytic benchmark bounds the stability of tables with no influential coordinate. Its contrapositive gives an influential entry. The hashing and hidden-coordinate arguments must then turn that entry into a source answer while keeping the decoding probability independent of alphabet size. The proof order is stability deficit, influential entry, locally recoverable answer, contradiction to the outer game. Skipping the middle passage would confuse a coordinate of a large table with a label of the original instance. (OpenAI, 2026a)

For Vertex Cover, the variance generated by an independent set gives large gradients after restriction. The compatibility constraint belongs to the joint gradient before separate conditioning. Conditional Jensen preserves sufficient squared mass when passing between these objects; the source then extracts bounded lists and compares their simultaneous-hit count with the outer soundness bound. Thus the crucial invariant is compatible list mass, not simply the existence of a large derivative at each vertex. (OpenAI, 2026d)

For Min-UnCut, fix the endpoint signs of one replacement path. If they have the demanded parity, alternating signs along the path cuts every edge. If they have the wrong parity, all edges cannot be cut, but alternating until the final edge leaves exactly one uncut edge. Minimizing over fresh internal vertices therefore reproduces the violated-comparison indicator exactly. Summing over disjoint path interiors preserves the weighted comparison cost without an additive error that could destroy the gap near zero. (OpenAI, 2026c)

For directed feedback deletion, the contradiction has a different form. A topological order produces one distribution of monotone functions, and its expected pivotality budget is bounded. Each selected bias forces another positive tail contribution for that same distribution. The identity $\mathbb{E}B={\int }_0^{\infty }\mathrm{Pr}(B>t)dt$ permits these contributions to be added. The common distribution is the mathematical reason that many scales contradict one budget. (OpenAI, 2026b)

See Also

• Perfect-completeness two-to-one games treats the exact value-one endpoint, with a different fiber constraint and a separate proof.
• Independent sets and three-colorability explains hardness with a structural promise on every vertex of a YES instance.
• Symmetric threshold widths develops influence and biased product measures in a probabilistic setting; here related quantities are used to decode labels.

🏷️ Manuscripts and verification scope

• The Unique Games Theorem — pinned manuscript and companion source.
• A Direct Proof of Optimal Max-Cut Hardness — pinned manuscript and companion source.
• The Factor-Two Hardness Threshold for Vertex Cover — pinned manuscript and companion source.
• Constant-factor hardness of Min-UnCut — pinned manuscript and companion source.
• Constant-factor hardness of directed feedback vertex set — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The page lists separate comparator statements for the Unique Games gap, Max-Cut, Vertex Cover, Min-UnCut, and directed feedback vertex set. It states reductions and gaps; no assumption that P differs from NP is built into those reductions. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. A Direct Proof of Optimal Max-Cut Hardness.

🐻  OpenAI 2026b. Constant-factor hardness of directed feedback vertex set.

🐻  OpenAI 2026c. Constant-factor hardness of Min-UnCut.

🐻  OpenAI 2026d. The Factor-Two Hardness Threshold for Vertex Cover.

🐻  OpenAI 2026e. The Unique Games Theorem.