lemmaroutineinferred_dep

Advice agreement decays with clean coordinates

Advice agreement decays exponentially in

k^{1/3}

when OPT ≤ 4/5

soundness side of the matrix gap

Lemma·lem:clean·§6.2 Vanishing advice on clean coordinates

Statement (paper)

\OPT(\mathcal E)\le 4/5

, every pair of local randomized strategies in the advice experiment satisfies

\Pr\bigl[\bar\pi(a_U)=a_O\bigr] \le \left(1-\frac{\beta\,2^{-\dim W-r_{\rm s}}}{3600}\right)^k \le \exp\!\left( -\frac{2^{-\dim W-r_{\rm s}}}{3600}\,k^{1/3} \right).

In particular, the upper bound tends to zero uniformly over the parity instance as

k

tends to infinity along cubes, with the advice spaces fixed.

In plain English

\OPT(\mathcal E)\le 4/5

, any pair of local randomized strategies in the advice experiment satisfies

\bar\pi(a_U)=a_O

with probability at most

(1-\beta 2^{-\dim W-r_{\rm s}}/3600)^k

, hence at most

\exp(-2^{-\dim W-r_{\rm s}}k^{1/3}/3600)

. So the bound goes to zero uniformly over the parity instance as

k\to\infty

along cubes, with the advice spaces fixed.

Why it's here

The proof finds the coordinates where the advice slope vanishes (clean coordinates). These behave as independent samples of the original game, so parallel repetition bounds the agreement probability given the clean set. Averaging over the binomial clean count gives a bound uniform in the advice

A

, which makes the advice unable to help the provers as

k

grows. The later matrix-gap proposition and the choice of

k

rely on this decay.}

Classified routine:

The decay bound comes from applying parallel repetition for projection games (Rao/Dinur–Steurer style bound) to the clean coordinates, then a Chernoff-type average over the binomial clean count. This is an adaptation of the standard argument showing that correlated advice cannot help the provers in a repeated game.

Uses

thmParallel repetition for projection gamesdefProjected advice experiment

Used by

propMatrix game completeness and soundness gapclaimChoosing the cube k and parity error

Inside the proof

claimAdvice coefficients are independent uniformclaimClean coordinates have ordinary question lawclaimClean pairs are independent game questionsclaimEach side reconstructs its advice inputclaimConditional agreement bounded by repeated gameclaimAveraging over binomial clean count

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,\gamma>0$ are fixed before the tuple length $k$ 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 $\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$ .
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.2 Vanishing advice on clean coordinates
Page: —
Label: lem:clean
Line: sections/05-clean.tex:88

Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

info
inferred_dep
critique: Lemma 6.2 bounds agreement "in the advice experiment". Its proof setup (sections/05-clean.tex:66-86) recalls the advice experiment of Section 5, which is Definition 5.2.