Unique Games and the limits of semidefinite relaxations

Max-Cut, integrality gaps, and optimal approximation

A proof of the Unique Games Conjecture would explain why certain semidefinite relaxations already attain the best possible worst-case polynomial-time approximation guarantees. It would not make stronger relaxations useless on particular instances.

Download the Quarto source

The result and its status

The collection released on 6 October 2026 includes The Unique Games Theorem and A Direct Proof of Optimal Max-Cut Hardness, both dated 23 September. The first claims a deterministic polynomial-time reduction from 3SAT to Unique Games with completeness arbitrarily close to one and soundness arbitrarily close to zero. The alphabet is fixed after those two error tolerances are chosen. The release’s formalization scope lists this gap reduction and the optimal Max-Cut hardness statement.

The implications below are conditional on the correctness of these newly released results. They do not depend on a new approximation algorithm: the algorithms and the earlier Unique-Games-conditional hardness reductions were already known.

Max-Cut: from signs to vectors

For an undirected graph with nonnegative edge weights, assign each vertex a sign x_i\in\{-1,1\}. An edge is cut precisely when its endpoint signs differ. Thus

\operatorname{OPT} =\max_{x\in\{-1,1\}^{V}} \sum_{\{i,j\}\in E}w_{ij}\frac{1-x_ix_j}{2}.

The Goemans–Williamson relaxation replaces signs with unit vectors v_i and replaces x_ix_j with \langle v_i,v_j\rangle. Equivalently, it optimizes over their Gram matrix:

\operatorname{SDP} =\max_{\substack{X\succeq 0\\X_{ii}=1}} \sum_{\{i,j\}\in E}w_{ij}\frac{1-X_{ij}}{2}.

Every sign assignment gives a feasible rank-one matrix X=xx^\top. Dropping the rank-one restriction enlarges the feasible set, so \operatorname{OPT}\leq\operatorname{SDP}. The relaxation is a tractable upper bound, not itself a cut.

To recover a cut, draw a random hyperplane through the origin and assign signs according to which side each vector lies on. If two vectors have angle \theta, their edge contributes (1-\cos\theta)/2 to the SDP, while the hyperplane separates them with probability \theta/\pi. Comparing these quantities gives

\alpha_{\mathrm{GW}} =\min_{0<\theta\leq\pi} \frac{2\theta}{\pi(1-\cos\theta)} =0.878567\ldots.

Consequently, in the ideal exact-SDP formulation, the rounded cut weight C satisfies

\mathbb E[C]\geq\alpha_{\mathrm{GW}}\operatorname{SDP} \geq\alpha_{\mathrm{GW}}\operatorname{OPT}.

Finite-precision polynomial-time implementations attain arbitrarily small slack in this guarantee. The ratio refers to the optimal cut weight, not the weight of all edges. It is an expectation over rounding, not a promise that every random draw achieves the bound.

An integrality gap is not an algorithmic lower bound

An integrality-gap construction exhibits graphs for which the SDP upper bound is substantially larger than the best actual cut. For the Goemans–Williamson SDP, the worst-case ratio \operatorname{OPT}/\operatorname{SDP} approaches \alpha_{\mathrm{GW}}.

That establishes a limitation of this relaxation. It does not, by itself, rule out a stronger relaxation, a different rounding analysis relative to the true optimum, or an unrelated algorithm with a better approximation guarantee.

The new Max-Cut manuscript claims the stronger statement: for every fixed \alpha>\alpha_{\mathrm{GW}} with \alpha\leq1, achieving an \alpha-approximation is NP-hard, even on simple unweighted graphs. In particular, a deterministic polynomial-time algorithm always returning a cut of weight at least \alpha\operatorname{OPT} would imply P=NP.

Previously, the sharp hardness threshold was known assuming Unique Games. A proof removes that additional conjecture. “Unconditional NP-hardness” does not establish P\ne NP; it establishes a reduction. A bounded-error randomized approximation algorithm beating the threshold would instead imply NP\subseteq BPP.

What stronger relaxations can still improve

The conclusion concerns a uniform worst-case approximation guarantee over all inputs. It does not assert that the basic SDP is the tightest bound on every graph.

• Individual instances. Extra valid inequalities or higher levels of a semidefinite hierarchy can tighten the upper bound and help recover better cuts.
• Restricted families. Graph structure, distributional assumptions, or additional promises can permit guarantees unavailable for unrestricted graphs.
• Certificates. A feasible cut and a certified relaxation upper bound can demonstrate near-optimality on the particular instance being solved.
• More computation. Hierarchy levels with superpolynomial cost, and exponential-time exact algorithms, are outside the polynomial-time restriction.

For example, a cut of weight 98 together with a certified SDP upper bound of 100 proves that the cut achieves at least 98\% of the true optimum. The universal 87.86\% approximation threshold does not prevent such an instance-specific certificate.

What a stronger relaxation cannot supply, under the hardness conclusion and the relevant complexity assumption, is an efficiently solvable and efficiently rounded method guaranteeing a ratio strictly above \alpha_{\mathrm{GW}} on every graph.

Beyond Max-Cut

Raghavendra’s 2008 theorem connects SDP integrality gaps to Unique-Games-conditional hardness for constraint satisfaction problems. For each fixed finite-domain, bounded-arity Max-CSP, a canonical SDP with an appropriate rounding procedure achieves the optimal polynomial-time worst-case approximation threshold, up to arbitrarily small slack, assuming Unique Games and the relevant complexity assumption.

A proof of Unique Games therefore turns a broad family of conditional approximation thresholds into ordinary NP-hardness results. The SDP and the rounding rule depend on the constraint language; there is no claim that any chosen relaxation works optimally. Nor does this classify arbitrary NP-hard optimization problems outside that framework.

The research implication is a distinction between improving a universal approximation factor and improving performance on the instances of interest. The former would encounter a sharp complexity barrier. The latter remains a substantial algorithmic and empirical problem.

References

1. OpenAI (2026). The Unique Games Theorem. Manuscript dated 23 September, released 6 October. Theorem 1.1 and Section 8.
2. OpenAI (2026). A Direct Proof of Optimal Max-Cut Hardness. Theorems 1.1–1.2; introduction reviews the Goemans–Williamson guarantee, SDP integrality gaps, and the earlier conditional hardness result.
3. Raghavendra, P. (2008). Optimal Algorithms and Inapproximability Results for Every CSP?. Proceedings of STOC. Theorems 1.1–1.2 and Corollary 1.3.