lemmaroutine

Subdivision yields unweighted simple game

Makes a weighted game unweighted and simple; unsatisfied fraction becomes  1/4
removes weights before taking the tensor power
Lemma·lem:unweighted-subdivision·§7.1 Removing weights and repeated edges

Statement (paper)

Let HH be a finite permutation-constraint game with h≥1h\ge1 positive rational occurrence weights summing to one. For every positive rational τ\tau, put Q=⌈h/τ⌉Q=\lceil h/\tau\rceil. There is a deterministic construction of an unweighted simple bipartite game BB with 4Q4Q edges and the same alphabet such that ∣val⁡(B)−(1−1−val⁡(H)4)∣≤τ4. \left|\val(B)-\left(1-\frac{1-\val(H)}4\right)\right| \le\frac{\tau}{4}. If the constraints of HH are translations on a finite binary vector space, so are those of BB. For fixed τ\tau, when HH is listed by its vertices, occurrences, permutation tables, and binary rational weights, the construction takes polynomial time in its encoding length.

In plain English

Given a permutation-constraint game HH with hh rational occurrence weights and a rational τ>0\tau>0, one can build deterministically an unweighted simple bipartite game BB with 4Q4Q edges, Q=⌈h/τ⌉Q=\lceil h/\tau\rceil, over the same alphabet, with val⁡(B)\val(B) within τ/4\tau/4 of 1−(1−val⁡(H))/41-(1-\val(H))/4. Translation constraints stay translations, and for fixed τ\tau the construction runs in polynomial time.

Why it's here

This lemma removes weights and repeated edges: it rounds the weights to multiples of 1/Q1/Q and subdivides each edge, so the game becomes unweighted and simple while the value changes in a controlled way (the unsatisfied fraction shrinks by a factor of 4, up to τ/4\tau/4 error). The final Unique Games reduction uses it to turn a matrix game into an unweighted simple bipartite game, and its tensor power then gives the output instance.
Classified routine:
Standard weight-rounding and edge-subdivision bookkeeping: weights are rounded to multiples of 1/Q and each constraint edge is replaced by a short path. This is a well-known technique for making constraint graphs unweighted and simple in Unique Games and label-cover reductions.

Uses

Nothing else in the paper

Used by

thmThe Unique Games TheoremclaimAlphabet-independent gap fixes repetition exponentclaimYES and NO values of the final gameclaimOutput is simple bipartite translation gameclaimPolynomial-time explicit encoding

Figures

A two-column flow diagram. The left column, "The reduction", has three boxes linked by solid arrows: 3SAT to a weighted parity gap instance, then the latent matrix test (stable nonlinear map, Lemma 3.1), then via "Rounding and subdivision; parallel repetition" to unweighted simple bipartite Unique Games (Theorem 1.1). The right column, "Soundness on a NO input", has two branches with dashed arrows: assuming test acceptance at least 0.99 gives decoded advice strategies with agreement at least $\gamma>0$ (Proposition 5.3), while a NO parity instance gives agreement at most $\exp(-ck^{1/3})$ for every pair of strategies (Lemma 6.2). Both branches point to a bottom box stating a contradiction for sufficiently large $k$: $\exp(-ck^{1/3})<\gamma$.
Figure 1diagramp. 6
The solid arrows describe the reduction; the dashed arrows describe its soundness argument. The decoding lower bound follows from high test acceptance, while the clean-coordinate upper bound follows from the NO parity gap and applies to every advice strategy. The constants c,γ>0c,\gamma>0 are fixed before the tuple length kk grows.
What it shows
A two-column flow diagram. The left column, "The reduction", has three boxes linked by solid arrows: 3SAT to a weighted parity gap instance, then the latent matrix test (stable nonlinear map, Lemma 3.1), then via "Rounding and subdivision; parallel repetition" to unweighted simple bipartite Unique Games (Theorem 1.1). The right column, "Soundness on a NO input", has two branches with dashed arrows: assuming test acceptance at least 0.99 gives decoded advice strategies with agreement at least γ>0\gamma>0 (Proposition 5.3), while a NO parity instance gives agreement at most exp⁡(−ck1/3)\exp(-ck^{1/3}) for every pair of strategies (Lemma 6.2). Both branches point to a bottom box stating a contradiction for sufficiently large kk: exp⁡(−ck1/3)<γ\exp(-ck^{1/3})<\gamma.
Read from the image by claude-opus-5.5 · confidence 88%
SupportsthmThe Unique Games TheoremlemLatent alphabet gadget with detecting noisepropMatrix test passing yields decoding strategieslemAdvice agreement decays with clean coordinatesthmGap hardness for weighted parity equationsthmParallel repetition for projection gameslemSubdivision yields unweighted simple gamepropMatrix game completeness and soundness gap

Sources

PaperOpen
Section
§7.1 Removing weights and repeated edges
Page
—
Label
lem:unweighted-subdivision
Line
sections/06-finish.tex:17
Leannot aligned

Phase 2 aligns this node to a Lean declaration.