propositionroutineinferred_dep

Matrix test passing yields decoding strategies

Passing the matrix test with probability 0.99 gives agreeing local strategies
decoding half of the matrix-game soundness
Proposition·prop:matrix-decoding·§5.2 The advice experiment and the decoding statement

Statement (paper)

Choose the latent and shortcode parameters in the order specified by Equation , fixing V=K⊕W\mathcal V=K\oplus W before kk. There are a constant γ>0\gamma>0 and an integer k0≥8k_0\ge8, depending only on these fixed parameters, with the following property. For every cube k≥k0k\ge k_0 and every parity instance, suppose a function FQ:Hom⁡(LQ,V)⟶K F_Q:\Hom(L_Q,\mathcal V)\longrightarrow K is given for every Q∈QkQ\in\mathcal Q_k. Assume folding for every such QQ, every P∈Hom⁡(LQ,V)P\in\Hom(L_Q,\mathcal V), and every c∈Kc\in K, and assume sharing for every permitted projection πˉ:LU→LO\bar\pi:L_U\to L_O and every P′∈Hom⁡(LO,V)P'\in\Hom(L_O,\mathcal V): FQ(P+ce0⊤)=FQ(P)+c,FU(P′πˉ)=FO(P′). \begin{aligned} F_Q(P+c e_0^\top)&=F_Q(P)+c,\\ F_U(P'\bar\pi)&=F_O(P'). \end{aligned} If this family passes the table test of Equation  with probability at least 0.990.99, then the projected advice experiment with β=k−2/3\beta=k^{-2/3} has local strategies whose probability of full answer agreement is at least γ\gamma.

In plain English

For large cubes kk, if tables FQ:Hom⁡(LQ,V)→KF_Q:\Hom(L_Q,\mathcal V)\to K satisfy folding (FQ(P+ce0⊤)=FQ(P)+cF_Q(P+ce_0^\top)=F_Q(P)+c) and sharing (FU(P′πˉ)=FO(P′)F_U(P'\bar\pi)=F_O(P')) and pass the matrix table test with probability at least 0.990.99, then the projected advice experiment with β=k−2/3\beta=k^{-2/3} has local strategies whose probability of full answer agreement is at least a constant γ>0\gamma>0.

Why it's here

This is the decoding statement that converts a nearly perfect table-test pass into a correlated pair of local strategies in the advice experiment. Its proof chains the good-advice lemma, the projected-TV and witness-transfer lemmas, and the Fourier coset decoding bound, so the constant γ\gamma depends only on the fixed parameters; later gap results rely on it to rule out high-passing tables when the game's value is low.
Classified routine:
This assembles earlier lemmas: good-row advice, projected total-variation and witness transfer, and the Fourier coset decoding bound. Chaining them into a decoding statement follows the standard soundness-analysis template of the 2-to-2 games proof (Khot–Minzer–Safra), with no new idea beyond those lemmas.

Uses

lemGood advice transfers to projected slicelemFourier decoding agrees with positive probabilitythmInverse shortcode theoremlemGood row advice is common and gives short answer setslemProjected matrix-test pair is nearly uniformdefProjected advice experiment

Used by

thmThe Unique Games TheorempropMatrix game completeness and soundness gapclaimChoosing the cube k and parity error

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
A flow diagram with a Referee box at top that samples $U,O,\bar\pi,A,T_O,M_O$, sets $S_O=AM_O$, and sends inputs down two parallel columns. The left column is the Equation decoder receiving $(U,A,T_U,S_U)$ with $T_U=T_O\bar\pi$, $S_U=S_O\bar\pi$; it picks a slice witness and answer set $\mathcal A=(z+Z)\cap\{v:e_0^\top v=1\}$ and samples $a_U$ uniformly from it. The right column is the Projected decoder receiving $(O,A,T_O,S_O)$; it sets $H=\ker A$, chooses $M_0$ with $AM_0=S_O$, samples $\sigma\in K^*$ and $\Phi$ with probability $|\widehat f_\sigma(\Phi)|^2$, and outputs $a_O=\Phi(h)$ for a fixed $h\in H$ with $\sigma(h)=1$. Both outputs satisfy $e_0^\top a=1$ and feed into a bottom box where the referee checks $\bar\pi a_U=a_O$.
Figure 3diagramp. 31
The two decoders use independent random tapes. Neither receives the sampled MOM_O or the projection πˉ\bar\pi; the right decoder chooses its own representative M0M_0 from the visible advice. Every displayed advice map includes its affine intercept, through the homogeneous coordinate. The transferred slice is used only to analyze these private rules: the right decoder does not use the left witness or answer set. If the left advice is not good, or if σ∣H=0\sigma|_H=0 on the right, that decoder returns an arbitrary valid answer.
What it shows
A flow diagram with a Referee box at top that samples U,O,πˉ,A,TO,MOU,O,\bar\pi,A,T_O,M_O, sets SO=AMOS_O=AM_O, and sends inputs down two parallel columns. The left column is the Equation decoder receiving (U,A,TU,SU)(U,A,T_U,S_U) with TU=TOπˉT_U=T_O\bar\pi, SU=SOπˉS_U=S_O\bar\pi; it picks a slice witness and answer set A=(z+Z)∩{v:e0⊤v=1}\mathcal A=(z+Z)\cap\{v:e_0^\top v=1\} and samples aUa_U uniformly from it. The right column is the Projected decoder receiving (O,A,TO,SO)(O,A,T_O,S_O); it sets H=ker⁡AH=\ker A, chooses M0M_0 with AM0=SOAM_0=S_O, samples σ∈K∗\sigma\in K^* and Φ\Phi with probability ∣f^σ(Φ)∣2|\widehat f_\sigma(\Phi)|^2, and outputs aO=Φ(h)a_O=\Phi(h) for a fixed h∈Hh\in H with σ(h)=1\sigma(h)=1. Both outputs satisfy e0⊤a=1e_0^\top a=1 and feed into a bottom box where the referee checks πˉaU=aO\bar\pi a_U=a_O.
Read from the image by claude-opus-5.5 · confidence 80%
SupportsdefProjected advice experimentlemFourier decoding agrees with positive probabilitypropMatrix test passing yields decoding strategieslemGood row advice is common and gives short answer setslemGood advice transfers to projected slice

Sources

PaperOpen
Section
§5.2 The advice experiment and the decoding statement
Page
—
Label
prop:matrix-decoding
Line
sections/04-matrix.tex:197
Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

  • info
    inferred_dep
    critique: Proposition 5.3 concludes that "the projected advice experiment with β=k^{-2/3} has local strategies" (sections/04-matrix.tex:220-222). That experiment is exactly Definition 5.2.