lemmaroutine

Unique Games with constant left degree and strong satisfaction

Gives simple Unique Games with constant left degree hh and strongly satisfied left side
UG input form for the later hardness reductions
Lemma·lem:simple-strong-left·§A.1 A simple strong-left form of Unique Games

Statement (paper)

Fix 0<ζ,ν<10<\zeta,\nu<1 and integers d,H≥1d,H\ge1. There are integers h,R≥1h,R\ge1, with h≥Hh\ge H and d∣hd\mid h, and a deterministic polynomial-time reduction from 3SAT\mathrm{3SAT} to nonempty explicit unweighted simple bipartite Unique Games instances Φφ=(A,B,E)\Phi_\varphi=(A,B,E) over [R][R] with the following properties. Every left vertex has degree hh. If φ\varphi is satisfiable, one labeling strongly satisfies at least a 1−ζ1-\zeta fraction of AA. If φ\varphi is unsatisfiable, then val⁡(Φφ)<ν\val(\Phi_\varphi)<\nu. The degree hh and the two errors used in Theorem  may be chosen from ζ,ν,d,H\zeta,\nu,d,H before that theorem supplies the alphabet RR.

In plain English

For fixed ζ,ν∈(0,1)\zeta,\nu\in(0,1) and d,H≥1d,H\ge1, 3SAT reduces in deterministic polynomial time to simple bipartite Unique Games instances over [R][R] in which every left vertex has degree hh (with h≥Hh\ge H and d∣hd\mid h). If φ\varphi is satisfiable, one labeling strongly satisfies at least a 1−ζ1-\zeta fraction of the left vertices; if not, the value is below ν\nu.

Why it's here

This converts the Unique Games Theorem, which only gives an ordinary value gap, into a strong-left form with constant left degree hh and a strongly-satisfied left side, which the later hardness consequences need. The proof normalizes weights into copies, rounds into an unweighted multigraph, tags right vertices, and keeps only sequences of hh occurrences with distinct tags to get a simple graph. The degree hh and the errors are fixed from ζ,ν,d,H\zeta,\nu,d,H before the theorem supplies RR.
Classified routine:
Follows from the Unique Games Theorem by standard regularization steps (weight normalization into copies, rounding to an unweighted multigraph, tagging right vertices, and taking degree-h sequences), in the spirit of Khot–Regev's strong/left-regular forms of UGC.

Uses

thmThe Unique Games Theorem

Used by

corGap hardness from a fixed SDP integrality gapcorOptimal hardness for ordering CSPspropFinite ordering transfer from Unique GamesclaimFixed-instance verifier gap from strong-left UGclaimExplicit polynomial-size occurrence listclaimParameter choices give final ordering gap

Inside the proof

claimParameters fixed before invoking UG theoremclaimCopy normalization to unit incident weightclaimRounding weights into unweighted multigraphclaimTagged right copies preserve valueclaimFull sequence graph value below 3ν/4claimDistinct-tag graph strongly satisfied on YESclaimNO soundness of the retained graphclaimConstruction runs in polynomial time

Sources

PaperOpen
Section
§A.1 A simple strong-left form of Unique Games
Page
—
Label
lem:simple-strong-left
Line
appendices/finite-consequences.tex:22
Leannot aligned

Phase 2 aligns this node to a Lean declaration.