Theoretical computer science · hardness of approximation · constraint satisfaction

Unique Games Conjecture

Collaboration beta

Can a computer efficiently distinguish a permutation-constraint graph in which almost all edges can be satisfied from one in which almost none can?

\forall ϵ > 0 \exists q = q (ϵ) : UG (1 - ϵ, ϵ, q) is NP-hard

Known results and sources

One-to-one permutation ribbons give each edge of a Unique Games instance its unique allowed label transfer.

Research problem

Exact mathematical statement

A Unique Games instance consists of a constraint graph $G=(V,E)$ , a finite alphabet $[q]$ , and a permutation $\pi_{uv}:[q]\to[q]$ for each oriented edge $(u,v)$ . A labeling $\ell:V\to[q]$ satisfies $(u,v)$ when

\ell(v)=\pi_{uv}(\ell(u)).

Its value is the largest satisfied-edge fraction achievable by one global labeling:

\operatorname{val}(U)=\max_{\ell:V\to[q]}\Pr_{(u,v)\in E}\left[\ell(v)=\pi_{uv}(\ell(u))\right].

The Unique Games Conjecture asks whether, for every $\varepsilon>0$ , there is a constant alphabet size $q=q(\varepsilon)$ for which it is NP-hard to distinguish

\operatorname{val}(U)\ge 1-\varepsilon \qquad\text{from}\qquad \operatorname{val}(U)\le \varepsilon.

The full one-to-one conjecture remains open. The proved 2-to-1/2-to-2 Games line with imperfect completeness is a neighboring variant and does not settle full UGC. The submitted tensor program is an unfinished route, not a proof.

Problem infographic

Problem at a glance

Scientific problem explainer for the open Unique Games Conjecture: a three-label edge displays the permutation 1 to 2, 2 to 3, and 3 to 1 with labels 2 and 3 satisfying the constraint; the game value maximizes the satisfied-edge fraction over one global labeling; the promised NP-hardness gap compares value at least 1 minus epsilon with value at most epsilon; a final band separates open full one-to-one UGC from the proved nearby 2-to-1 and 2-to-2 Games variant with imperfect completeness. — A Unique Games edge permits exactly one neighboring label for each starting label; the open conjecture asks for NP-hardness across the promised near-one versus near-zero value gap.

Current mathematical picture

Where work on Unique Games Conjecture stands

Recent proof claim under review

The current work develops a tensor-rank-one local verifier program for the full one-to-one Unique Games Conjecture. It reports exact local spectrum, balanced-optimality and decoder footholds, a complete partition-rank-one spectral layer, full-secant algebra, and four finite computations, while explicitly withholding independent verification. A Walsh-mask counterexample eliminates arbitrary Fourier-subprojection routes. The active local gate is a bounded-load affine plane-container theorem; a separate outer-PCP list-synchronization and alphabet-control gate would still remain before UGC hardness. The conjecture is unresolved.

Strongest supported footholdExact local spectrum and balanced top band

The current work derives the exact rank-one-walk eigenvalues, a pure/non-pure gap, and sharp balanced optimality of honest contractions.

Evidence posture · Reported result

Leading routeLocal spectrum to complete affine supports

Use the exact spectrum, top-band decoders, partition-rank cutoff, conditional analytic-rank compression, and only complete affine frequency supports to reach a bounded-zoom local inverse theorem.

Route status · Active route

Useful failureArbitrary-mask and selector routes

Arbitrary low-rank subprojections, selector lifts, first-pattern assignments, and coefficient-deletion monotonicity are eliminated by the Walsh-mask counterexample.

Route status · Eliminated route

Main reductionComplete partition-rank-one spectral layer

The current work gives a spectral cutoff, a complete-support L⁴ estimate, and a dimension-free grouped-contraction inverse theorem for the first full spectral layer.

Evidence posture · Reported reduction

Completed special caseFive-term Segre-circuit budget

For a minimal five-term pure-tensor relation over F₂, the sum of mode-span excesses satisfies Σ_i(r_i−1)≤3; the current work further lists five normal-form families.

Evidence posture · Source-reported route statement

Priority open bridgeProve the R=2 two-cut plane-container theorem

For Σ_{π,τ}, classify high mixed-decomposition multiplicity, force a complete affine container or bounded pair-codegree, and construct exact bounded-load fractional weights, using an exact orbit-reduced rational LP only as a finite guide.

Task status · Work already reported in progress

Research-record correctionResearch-record correction

We corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Reader-facing record corrected; mathematics unchanged

Work mapped so far

Unique Games Conjecture in numbers

1.5kretained lines of mathematical investigation1,512 in the current working snapshot

Argument development: 1,313 · 87%
Explored or eliminated routes: 37 · 2%
Computational analysis: 27 · 2%
Open obligations: 37 · 2%
Definitions and setup: 98 · 6%

24selected mapped statements5routes investigated6reported milestones6open questions2contribution-ready tasks

How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Proposed bySubhash KhotProposed2002Status checkedAug 6, 2026

Source recordedAug 6, 2026

Recommended next task

Audit the external theorem inputs

Supply exact primary sources, hypotheses, fields, normalizations, constants, stabilizer conventions, and restriction-globalness for linear Kneser, analytic-rank/partition-rank, and complete fixed-cut matrix-rank hypercontractivity.

Suggested move: Write the exact imported statements and check scalar extension, stabilizers, zero coordinates, affine restrictions, and tensor normalizations against the current work's conventions.

What would count as progress

Each named import has a primary citation and verbatim theorem statement.
Field, normalization, constants, and every packet use are matched explicitly.
The length-eight and all-length Kneser consequences are separated from the independently finite length-five and length-six checks.

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

22 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

Scroll horizontally to explore the route

Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Active routeLocal spectrum to complete affine supports

Use the exact spectrum, top-band decoders, partition-rank cutoff, conditional analytic-rank compression, and only complete affine frequency supports to reach a bounded-zoom local inverse theorem.

Route status · Active route

Active routePlane-container route

The primary local route seeks an exact bounded-load cover of structured affine 2-planes in bounded-partition-rank sets, leaving only bounded pair-codegree residuals.

Route status · Active route

Active routeOuter-PCP composition

After a stable quantitative local inverse theorem, independently prove list extraction, synchronization, folding, smoothness, agreement decoding, and alphabet control.

Route status · Active route

Explored alternatives

Other routes

2 recorded

Narrowed routeFull-secant fourth-moment route

Full-secant graph and circuit algebra remain useful, but the global fourth-moment bound is narrowed to a candidate pending the length-eight Kneser input and exact complete-support audit.

Route status · Narrowed route

Eliminated routeArbitrary-mask and selector routes

Arbitrary low-rank subprojections, selector lifts, first-pattern assignments, and coefficient-deletion monotonicity are eliminated by the Walsh-mask counterexample.

Route status · Eliminated route

Route statements and reductions

Statements the next route can inspect and build on

Route statementExact local spectrum and pure/non-pure gap

Characters χ_S are eigenfunctions of the rank-one walk with eigenvalue equal to the tensor bias. A nonzero pure frequency has λ⋆=1−2^{1−d}; every non-pure frequency has λ(S)≤1−3·2^{−d}, leaving an ambient-dimension-independent gap 2^{−d}.

Source-reported route statement

Route statementExact top-band contraction-fiber decoder

If 0<μ<1/2 and every nonzero Fourier frequency of 1_A−μ is pure, some basic contraction fiber has A-density at least μ+(1−2μ)/d. This is a fiber-density conclusion, not global dictatorship.

Source-reported route statement

Route statementFirst full spectral-layer inverse theorem

Combining the partition-rank cutoff and complete L⁴ bound yields a dimension-free one-grouped-contraction inverse theorem above τ_d, under the current work's explicit density and retention hypotheses.

Source-reported route statement

Route statementSimultaneous-flattening compression

Rank-minimal decompositions of one bridge tensor across two distinct bipartitions lie in a four-block common-refinement box with each block dimension at most mn; a fourth-moment bridge therefore has a 16⁴ finite core.

Source-reported route statement

Route statementSafe complete affine-coset projection bound

If C=γ+H is a complete affine coset whose direction H is an allowed R-zoom character space, then ||P_Cg||∞≤2σ_R(A) and ||P_Cg||₄⁴≤4σ_R(A)²||P_Cg||₂². The source explicitly excludes arbitrary subsets of a coset.

Source-reported route statement

Route statementConditional collective-bias compression

Assuming a dimension-free analytic-rank-to-partition-rank bound F_{d+1}, every frequency subspace with average eigenvalue at least η contains a codimension-at-most F_{d+1}(log₂(1/η)) subspace that is the exact character space of a bounded grouped-contraction zoom.

Source-reported route statement · dependencies incomplete

Route statementFractional affine-container fourth-moment reduction

An exact fractional cover of structured affine 2-planes by complete affine subspaces with point load L, plus a residual pair-codegree bound D, yields ||q||₄⁴≤(3+2D)E²+4Lσ_Z(A)²E.

Source-reported route statement

Route statementBounded-partition-rank plane-container gate

For fixed d and R, the open local gate is to split affine 2-planes in Γ_R={S:prank(S)≤R} into a bounded-pair-codegree residual and a structured family with an exact bounded-point-load fractional cover by complete affine subspaces in Γ_R.

Source-reported route statement · dependencies incomplete

Route statementConditional local inverse theorem at positive thresholds

If the plane-container theorem holds for every fixed R and the required analytic-rank-to-partition-rank theorem is supplied, then the current work derives a bounded-zoom inverse theorem at every positive spectral threshold.

Source-reported route statement · dependencies incomplete

Route statementIndependent outer-PCP composition gate

Even after a local inverse theorem, a UGC proof would still require a quantitative outer projection-game composition with folding/balance, list extraction, synchronization, agreement decoding, and alphabet-size control.

Source-reported route statement · dependencies incomplete

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

6 featured tasks

Audit the external theorem inputs

Ready to work on

Complete the full-secant support and length-eight audit

For star, double-star, 3+3, and 4+4 local polynomials, record exact Fourier supports and prove they are complete affine cosets or bounded Boolean combinations; separately pin down the length-eight Kneser input.

Suggested move: Audit the support ledger row by row; where a genuine selector remains, replace it with a fractional-container argument.

Ready to work on

Complete the independent outer-PCP composition

After a stable local theorem, instantiate a smooth outer projection game and prove folding, list extraction, cross-edge synchronization, agreement decoding, and final alphabet control as functions only of ε.

Suggested move: Begin only after the local inverse theorem has a stable quantitative statement.

Blocked by the current route

Propagate explicit local inverse and list parameters

Once plane-container control and analytic-rank/partition-rank inputs are stable, derive explicit μ, zoom-density, and list-size parameters at every positive spectral threshold.

Suggested move: Wait for a stable PC(R) theorem and audited analytic-rank input, then propagate all constants without hiding dimension dependence.

Blocked by the current route

Generalize plane containers to every fixed partition-rank budget

After the R=2 two-cut case, induct on active cuts and total partition-rank budget while preserving complete algebraic supports.

Suggested move: Establish the two-cut R=2 base case before designing the induction over active cuts and rank budget.

Blocked by the current route

Prove the R=2 two-cut plane-container theorem

Suggested move: Parameterize natural R+S containers, count decompositions and plane completions, classify the high-multiplicity locus, and solve the exact symmetry-reduced container LP or retain its dual obstruction.

Work already reported in progress

Sourced mathematical context

The known mathematical landscape

Context collected Aug 6, 2026

Current statusRecent proof claim under review

The full Unique Games Conjecture remains open: a 2025 peer-reviewed exposition still states the 1-to-1 near-perfect-completeness/near-zero-soundness problem as a conjecture and distinguishes it from the proved 2-to-1/2-to-2 line. A 2026 Vertex Cover paper claims a disproof via a pointwise strict sub-2 approximation, but its public statement does not provide the fixed uniform 2-eta factor required to contradict the Khot-Regev UGC consequence, and no independent acceptance of the claimed disproof was located.

[10][12][13]

External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

2026
Peer reviewedA Vertex Cover article claims that its pointwise strict sub-2 approximation disproves UGC. The stated guarantee does not exhibit the fixed uniform 2-eta approximation factor excluded by the Khot-Regev conditional barrier, so the claimed consequence remains unverified and statement-misaligned.[12][13]
2025
Peer reviewedA current Theory of Computing exposition states the Unique Games Conjecture as an unresolved conjecture and reports no consensus on its validity while explaining how the proved 2-to-1/2-to-2 line differs from UGC.[10]
2023
Peer reviewedKhot, Minzer, and Safra completed the 2-to-2 Games Conjecture with imperfect completeness, yielding stronger Vertex Cover and Unique Games hardness gaps. The 2025 companion exposition distinguishes this weaker-variant theorem from the full 1-to-1 UGC.[9][10]
2015
Peer reviewedArora, Barak, and Steurer published subexponential-time algorithms for Unique Games and Small-Set Expansion. The paper explicitly states that these results stop short of refuting UGC.[7]

Mathematical neighborhood

Related results and reusable starting points

Current focusUnique Games Conjecture

Equivalent formulationMAX-2LIN(q) gap hardness

The near-1 versus near-0 hardness formulation for MAX-2LIN(q), with q allowed to depend on the gap parameters, is equivalent to UGC through known reductions.

[3]

Solved special caseperfectly satisfiable unique games

When the unique game has value exactly 1, a satisfying labeling can be found in polynomial time by trying a label in each connected component and propagating it through permutation constraints. UGC necessarily uses imperfect completeness.

[2]

Solved special caseUnique Games on expanding constraint graphs

Unique Games instances whose constraint graphs have suitable expansion admit polynomial-time algorithms; arbitrary constraint graphs remain outside this solved class.

[5]

Dependency or reductionSmall-Set Expansion hypothesis

The Small-Set Expansion hypothesis implies the Unique Games Conjecture via a reduction. Because Small-Set Expansion is itself conjectural, this does not prove UGC.

[6]

Weaker or relaxed form2-to-1 and 2-to-2 Games theorem

The proved 2-to-2 Games result, also presented through the 2-to-1 Games line with imperfect completeness, relaxes the one-to-one permutation constraint central to Unique Games. Its proof gives important hardness progress but not full UGC.

[9][10]

Logical consequenceoptimal hardness of approximation consequences

UGC implies sharp conditional inapproximability thresholds for MAX-CUT, Vertex Cover, and broad CSP classes. Those reductions transfer truth of UGC to hardness consequences; the consequences are not themselves established unconditionally by these papers.

[3][4]

Related problemQuantum Unique Games Conjecture

The Quantum Unique Games Conjecture concerns quantum extensions of Label Cover and Unique Label Cover. It is a separately formulated quantum complexity conjecture, not a reformulation or solution of classical UGC.

[11]

Formal and computational footholds

Existing statements, libraries, computations, and datasets that can shorten the next serious attempt.

software · not independently reproducedHallelujah: Approximate Vertex Cover Solver
The author provides Python code associated with the claimed pointwise strict sub-2 Vertex Cover algorithm. ProofAtlas did not reproduce it, and code or benchmark performance does not establish the fixed uniform 2-eta guarantee needed to contradict the UGC-based Vertex Cover hardness result.
[13][14]

Formalization opportunities

Lean work can make these reusable foundations precise without being presented as a proof of the core problem.

Formalization targetA checked finite definition of Unique Games or unique Label Cover instances, permutation constraints, labelings, and game value.
Formalization targetFormal promise-problem and polynomial-time reduction infrastructure capable of stating NP-hardness with quantified completeness, soundness, and alphabet-size parameters.
Formalization targetA reviewed formal statement-alignment proof connecting any imported PCP, gap amplification, or hardness theorem to the exact standard UGC quantifier order.

Research-record corrections

What changed in the research record

These notes describe corrections to cited passages, highlighted tasks, or connections between claims. The mathematical claims and their status did not change.

Research-record correctionWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

The initial argument structure appears separately. Uploads, model runs, and presentation changes do not count as mathematical updates.

How the route was assembled

Argument structure

These stages follow the mathematical order of the supplied argument.

7 mapped milestonesretained argument map

Browse all 7 mapped stages

stage 1Exact local spectrum and balanced top band
stage 2Contraction-fiber decoder footholds
stage 3Complete partition-rank-one spectral layer
stage 4Full-secant algebra and finite cases
stage 5Arbitrary-mask route eliminated
stage 6Two-cut compression and finite 2-versus-1 pilot
stage 7Plane-container and outer-PCP gates isolated

Exact local spectrum and balanced top bandThe current work derives exact rank-one-walk eigenvalues and sharp balanced optimality for honest contractions.