The Unique Games Conjecture and optimal approximation thresholds

2 · Going further

The main manuscript states that, for every fixed $\epsilon ,\delta \in (0,1/2)$, there is a deterministic polynomial-time reduction from 3SAT to Unique Games over a fixed finite alphabet. Its completeness is at least $1-\epsilon$, and its soundness is at most $\delta$. In the language of the reduction, satisfiable inputs lead to instances where almost all constraints can be satisfied, while unsatisfiable inputs lead to instances where at most a small fraction can be satisfied. The parameters are fixed in advance; the statement does not claim one fixed alphabet works for every choice of them.

The source identifies this as a resolution of Khot's Unique Games Conjecture. The central mechanism described in the abstract is the gap-producing reduction itself: it transforms the original decision problem into a sharp contrast between high and low achievable satisfaction. No construction details are supplied in the abstract, so the source does not support a more detailed account of how that gap is obtained.

The companion manuscripts report independent direct reductions using established PCP and Label Cover hardness results. For Max-Cut, the stated barrier is approximation within any fixed factor greater than the Goemans–Williamson constant, on simple unweighted graphs. For minimum Vertex Cover, it is every fixed factor below two, again on simple unweighted graphs. Both manuscripts are marked as Lean-formalized.

The remaining manuscripts claim NP-hardness of approximating Min-UnCut within every fixed factor $C>1$, even on simple undirected unweighted graphs, and of approximating minimum directed feedback vertex set within any fixed constant factor, even on unweighted digraphs. These two manuscripts are not marked as Lean-formalized. Their role in the family is to extend the reported approximation barriers through direct arguments, not to supply steps needed for the main Unique Games result.

Useful notions

• Decision problems and optimization problems
• Polynomial-time reductions
• Approximation factors
• Constraint satisfaction
• Graphs and directed graphs

What was known before / what is new

Limits and assumptions

The Unique Games statement requires fixed parameters $\epsilon ,\delta \in (0,1/2)$ and a fixed finite alphabet. The graph statements concern fixed approximation factors, with the directions of the inequalities differing between Max-Cut and the minimization problems; the stated Max-Cut and Vertex Cover claims do not include equality at their thresholds. Min-UnCut explicitly requires $C>1$. The main result has a Lean formalization, and the Max-Cut and Vertex Cover manuscripts are also labelled Lean-formalized, but the supplied source does not describe the formalizations' internal scope or coverage of auxiliary claims. Min-UnCut and directed feedback vertex set are manuscript claims without a stated Lean formalization. The source lists no remaining open questions.

Mini glossary

Polynomial-time reduction

—

A transformation from one problem to another whose running time is bounded by a polynomial in the input size.

Completeness

—

Here, a guarantee on how large a fraction of constraints can be satisfied in the output when the original 3SAT input is satisfiable.

Soundness

—

Here, a bound on how large a fraction of constraints can be satisfied in the output when the original 3SAT input is unsatisfiable.

Approximation factor

—

A multiplicative measure of how close an algorithm's answer is to the best possible answer, with the convention depending on whether the objective is maximized or minimized.

NP-hardness

—

A complexity classification expressing that a task is at least as hard as the problems in NP under the relevant reductions.

Lean formalization

—

An encoding of mathematical statements and their proofs for checking in the Lean proof assistant.

Keywords : Unique Games · Approximation hardness · Lean formalization

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Manuscripts in this family