propositionroutine

Matrix game completeness and soundness gap

Matrix game has value ≥ 1−kξ−p∗/21-k\xi-p_*/2 if satisfiable, ≤ 99/100 otherwise
supplies the gap for subdivision and repetition
Proposition·prop:matrix-gap·§6.3 The matrix-game gap

Statement (paper)

Fix p∗>0p_*>0 and choose the latent and shortcode data in the order of Equation . For every sufficiently large cube kk, the matrix game G\mathcal G constructed from a weighted parity instance E\mathcal E with distinct positions satisfies OPT⁡(E)≥1−ξ⟹val⁡(G)≥1−kξ−p∗/2,OPT⁡(E)≤4/5⟹val⁡(G)≤99/100. \begin{aligned} \OPT(\mathcal E)\ge1-\xi &\quad\Longrightarrow\quad \val(\mathcal G)\ge1-k\xi-p_*/2,\\ \OPT(\mathcal E)\le4/5 &\quad\Longrightarrow\quad \val(\mathcal G)\le99/100. \end{aligned} The lower threshold on kk depends only on the fixed latent and shortcode data, not on E\mathcal E or ξ\xi.

In plain English

For all sufficiently large cubes kk (threshold depending only on the fixed latent and shortcode data), the matrix game G\mathcal G built from a weighted parity instance E\mathcal E with distinct positions has value at least 1−kξ−p∗/21-k\xi-p_*/2 when OPT⁡(E)≥1−ξ\OPT(\mathcal E)\ge 1-\xi, and value at most 99/10099/100 when OPT⁡(E)≤4/5\OPT(\mathcal E)\le 4/5.

Why it's here

This combines completeness (Lemma 4.3, which gives the 1−kξ−p∗/21-k\xi-p_*/2 bound) with soundness: if G\mathcal G had value above 99/10099/100, the table-decoding proposition would produce correlated local strategies agreeing with constant probability γ\gamma, contradicting the decay of advice agreement in the clean-coordinates lemma once kk is large. It yields a gap with adjustable completeness through p∗p_*, which the final choice of kk and the Unique Games theorem use.
Classified routine:
Direct combination of the completeness lemma (Lemma 4.3) with the matrix-decoding proposition and the clean-coordinates decay lemma, via a standard contradiction once kk is large; the proof only assembles these earlier nodes.

Uses

lemCompleteness of the latent matrix testpropMatrix test passing yields decoding strategieslemAdvice agreement decays with clean coordinates

Used by

thmThe Unique Games TheoremclaimChoosing the cube k and parity errorclaimYES and NO values of the final game

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
§6.3 The matrix-game gap
Page
—
Label
prop:matrix-gap
Line
sections/05-clean.tex:243
Leannot aligned

Phase 2 aligns this node to a Lean declaration.