lemmaroutineinferred_dep

Good advice transfers to projected slice

Good advice witness transfers to the projected slice with agreement ≥

\alpha/4

gives the slice correlation for Fourier decoding

Lemma·lem:projected-witness·§5.5 Transferring the chosen slice

Statement (paper)

Suppose the matrix-test acceptance is at least

0.99

. For all sufficiently large cubes

k

, a set of probability at least

\gamma_1=\frac{\alpha g_0}{8}\,2^{-\ell r_{\rm s}}>0

of the joint data

D

in Definition has the following properties. The padded

U

-advice is good, with the chosen answer set

\mathcal A

and its certifying witness. Writing

z'=\bar\pi z

, that witness transfers to a nonempty slice

AM_O=S_O,\qquad M_O\bar\pi q_j=t_j,

on which

\Pr\bigl[F_O(M_O,T_O)=M_Oz'+u\mid AM_O=S_O,\ M_O\bar\pi q_j=t_j\text{ for all }j\bigr] \ge\alpha/4.

The probability in this equation is taken over a uniform matrix in the specified slice.

In plain English

If the matrix test accepts with probability at least

0.99

and

k

is large, then with probability at least

\gamma_1=\frac{\alpha g_0}{8}2^{-\ell r_{\rm s}}

over the joint data

D

, the padded

U

-advice is good with answer set

\mathcal A

and witness, and the witness transfers to a nonempty slice

AM_O=S_O

M_O\bar\pi q_j=t_j

on which

F_O(M_O,T_O)=M_Oz'+u

with conditional probability at least

\alpha/4

Why it's here

This lemma moves the good-advice witness, found for the

U

-side data, onto the slice of

M_O

that the

O

-prover actually sees, so a correlation of size

\alpha/4

holds there. It combines the

g_0

mass of good advice from the good-row-advice lemma with the near-uniformity of the projected pair

(M_O\bar\pi,T_O\bar\pi)

from the projected-TV lemma, at a constant-factor loss. The resulting slice is the input for the Fourier coset decoding and matrix decoding steps.

Classified routine:

It follows directly by combining the good-row-advice lemma (mass

g_0

) with the projected-TV near-uniformity lemma, using a total-variation transfer and Markov/averaging that costs only a constant factor. This is standard bookkeeping, not a new idea.

Uses

lemGood row advice is common and gives short answer setslemProjected matrix-test pair is nearly uniformdefProjected advice experiment

Used by

thmThe Unique Games TheorempropMatrix test passing yields decoding strategieslemFourier decoding agrees with positive probabilityclaimChoosing the cube k and parity errorclaimSlice correlation survives nontrivial restriction

Figures

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 $M_O$ or the projection $\bar\pi$ ; the right decoder chooses its own representative $M_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 $\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,\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$ .
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.5 Transferring the chosen slice
Page: —
Label: lem:projected-witness
Line: sections/04-matrix.tex:543

Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

info
inferred_dep
critique: The statement of Lemma 5.7 (sections/04-matrix.tex:552) says "of the joint data D in Definition ". The definition is currently flagged as an orphan.