Open problem, Applied and computational mathematics, posed 2002

Unique games conjecture

Open

For every $\varepsilon > 0$ , there exists an alphabet size $k = k(\varepsilon)$ such that given a unique label cover instance over an alphabet of size $k$ (where each constraint between two variables $u, v$ is a bijection $\pi_{u,v} : [k] \to [k]$ ), it is NP-hard to distinguish whether there is a labeling satisfying at least a $1 - \varepsilon$ fraction of the constraints or no labeling satisfies more than an $\varepsilon$ fraction of the constraints.

Research frontier as of 2026

As of 2026, the full Unique Games Conjecture with $1$ -to- $1$ constraints remains open. The landmark 2018 resolution of the $2$ -to- $2$ Games Conjecture by Khot, Minzer, and Safra proved NP-hardness of distinguishing $(1/2 - \varepsilon)$ -satisfiable from $\varepsilon$ -satisfiable unique games, yielding unconditional hardness of approximation near $\sqrt{2}$ for Vertex Cover, while bridging the gap from completeness $1/2$ to $1 - \varepsilon$ remains the central challenge.

Best known results

The $2$ -to- $2$ Games Theorem (Khot–Minzer–Safra 2018) proves that for every $\varepsilon > 0$ , it is NP-hard to distinguish Unique Games instances with value at least $1/2 - \varepsilon$ from those with value at most $\varepsilon$ .
Subexponential-time algorithms (Arora–Barak–Steurer 2010) solve Unique Games with completeness $1 - \varepsilon$ in time $\exp(k \cdot n^{\varepsilon^{O(1)}})$ using spectral graph partitioning and the Lasserre/Sum-of-Squares hierarchy.

Tools and where they stop

Tool	Achieved	Where it stops
Discrete Fourier analysis on the Boolean hypercube and Majority Is Stablest	Translates the Unique Games Conjecture into tight inapproximability bounds for Max-Cut, Max-2SAT, and general constraint satisfaction problems via dictatorship tests	Proves conditional hardness assuming UGC, rather than proving the NP-hardness of Unique Games itself
Grassmann graph expansion and non-abelian Fourier analysis	Characterizes non-expanding sets in the Grassmann graph via zoom-in and zoom-out structure, proving the $2$ -to- $2$ Games Conjecture	Inherently loses a factor of $2$ in completeness when reducing from $2$ -to- $2$ constraints to $1$ -to- $1$ bijective constraints, stalling at completeness $1/2 - \varepsilon$

Open questions

Does the Unique Games Conjecture hold with completeness $1 - \varepsilon$ for every $\varepsilon > 0$ , or does there exist a polynomial-time algorithm distinguishing $(1 - \varepsilon)$ -satisfiable instances from $\varepsilon$ -satisfiable ones?

References

Subhash Khot (2002). On the power of unique 2-prover 1-round games · DOI:10.1145/509907.510017
Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell (2007). Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? · DOI:10.1137/S0097539705447372
Prasad Raghavendra (2008). Optimal algorithms and inapproximability results for every CSP? · DOI:10.1145/1374376.1374414
Subhash Khot, Dor Minzer, Muli Safra (2023). Pseudorandom sets in Grassmann graph have near-perfect expansion · DOI:10.4007/annals.2023.198.1.1