MathDB

Unique-Games Conjecture

From papers

A Unique-Games instance is a 1-to-1 Games instance: a 2-Prover-1-Round Games instance in which the two alphabets have equal size and every constraint is a bijection between them. For ε,s>0\varepsilon,s>0, let nn be the alphabet size. Unique-Games Conjecture. For all ε,s>0\varepsilon,s>0, there is n∈Nn\in\mathbb{N} such that, given a Unique-Games instance Ψ\Psi with alphabet size nn, it is NP-hard to distinguish between the following cases: there is an assignment to Ψ\Psi satisfying at least 1−ε1-\varepsilon fraction of the constraints, and there is no assignment to Ψ\Psi satisfying more than an ss fraction of the constraints. The conjecture is presented as the standard imperfect-completeness hardness assumption for Unique Games. The supplied status evidence does not resolve this conjecture.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Equivalent formulations 1

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

  1. The Unique Games Conjecture

    Let an instance of the Unique Games Problem consist of a graph, a set of colors, and a matching of the colors for each edge. The value of an instance is the largest fraction of edge constraints that can be satisfied by a coloring. Unique Games Conjecture. For every ε>0\varepsilon>0, distinguishing whether the instance has value at least 1−ε1-\varepsilon or value at most ε\varepsilon is NP-hard. This conjecture is central to hardness-of-approximation results; in particular, the source states that achieving an approximation ratio for Max-Cut better than αGW\alpha_{GW} is UG-hard, so the conjecture is not being presented as an unresolved claim here.

    source: Afonso S. Bandeira, Amit Singer and Thomas Strohmer, “Mathematics of Data Science”, arXiv:2607.11938 (2026).

Sources & referencesView supporting material

Primary source

Mark Braverman, Subhash Khot, Noam Lifshitz and Dor Minzer, “An Invariance Principle for the Multi-slice, with Applications”, arXiv:2110.10725 (2025).

complexity-theoryconstraint-satisfactionhardness-of-approximationunique-games

Solutions 0

No solutions have been posted yet.