definitionroutine

Projected advice experiment

Defines the advice game: provers share AA and projected data, must agree
setting for decoding, witness transfer and clean bound
Definition·def:projected-advice·§5.2 The advice experiment and the decoding statement

Statement (paper)

Sample U,O,πU,O,\pi, then an independent uniform map A:K→F2rsA:K\to\F_2^{r_{\rm s}} and independent uniform maps TO:LO→W,MO:LO→K. T_O:L_O\to W,\qquad M_O:L_O\to K. Put SO=AMOS_O=AM_O and send the following inputs to the two provers: U-prover:(U,A,TOπˉ,SOπˉ),O-prover:(O,A,TO,SO). \begin{aligned} &\text{$U$-prover:}&& (U,A,T_O\bar\pi,S_O\bar\pi),\\ &\text{$O$-prover:}&& (O,A,T_O,S_O). \end{aligned} The map MOM_O beyond the stated advice is hidden. Each prover returns an actual answer, that is, a vector of first bit one in its homogeneous answer space. They succeed when their answers aU,aOa_U,a_O satisfy πˉaU=aO\bar\pi a_U=a_O.

In plain English

The advice experiment samples U,O,πU,O,\pi and independent uniform maps A:K→F2rsA:K\to\F_2^{r_{\rm s}}, TO:LO→WT_O:L_O\to W, MO:LO→KM_O:L_O\to K, and sets SO=AMOS_O=AM_O. The UU-prover receives (U,A,TOπˉ,SOπˉ)(U,A,T_O\bar\pi,S_O\bar\pi) and the OO-prover receives (O,A,TO,SO)(O,A,T_O,S_O); each returns an actual answer (first bit one in its homogeneous answer space), and they succeed if πˉaU=aO\bar\pi a_U=a_O.

Why it's here

This defines the two-prover game used for the decoding statement: both provers see the shared advice AA and the projected data TO,SOT_O,S_O, while MOM_O stays hidden. The matrix-decoding proposition, the witness-transfer lemma and the clean-coordinate bound all analyze strategies in this experiment, so it fixes the setting and the success event πˉaU=aO\bar\pi a_U=a_O.
Classified routine:
A new auxiliary two-prover game set up for the paper's decoding step. It adapts the advice/zoom-in style experiments from the 2-to-2 Games proof (Khot–Minzer–Safra and coauthors) for analyzing projection strategies, so it is a bookkeeping definition rather than a new idea in itself.

Uses

Nothing else in the paper

Used by

propMatrix test passing yields decoding strategieslemGood advice transfers to projected slicelemAdvice agreement decays with clean coordinates

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 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
def:projected-advice
Line
sections/04-matrix.tex:168
Leannot aligned

Phase 2 aligns this node to a Lean declaration.