theoremstandardstructure_uncertain

Parallel repetition for projection games

Value ≤ 1−g1-g gives (1−g2/16)n(1-g^2/16)^n under nn-fold repetition of projection games
amplifies constant gaps independent of the alphabet
Theorem·thm:repetition·§6.1 Classical projection-game repetition

Statement (paper)

Let GG be a finite bipartite projection game, with an arbitrary probability distribution on its constraint occurrences. Question sets and answer alphabets may be arbitrary finite sets, and parallel constraint occurrences are allowed. The game G⊗nG^{\otimes n} samples nn independent occurrences, sends each prover its tuple of questions, and accepts if all nn projection constraints hold. For every integer n≥1n\ge1 and every 0<g<10<g<1, val⁡(G)≤1−g⟹val⁡(G⊗n)≤(1−g2/16)n. \val(G)\le 1-g \quad\Longrightarrow\quad \val(G^{\otimes n})\le (1-g^2/16)^n. The bound is independent of the question-set and alphabet sizes.

In plain English

If a finite bipartite projection game GG has value at most 1−g1-g, then the nn-fold parallel repetition G⊗nG^{\otimes n} has value at most (1−g2/16)n(1-g^2/16)^n. The bound does not depend on the sizes of the question sets or answer alphabets.

Why it's here

This is the classical alphabet-independent parallel repetition theorem for projection games, imported as the amplification tool of the paper. Any constant gap in a projection game yields exponentially decaying value under repetition at a rate fixed by the gap alone, which is what the later arguments (the clean-coordinate bound and the final YES/NO analysis of the repeated game) need.
Classified standard:
Alphabet-independent parallel repetition for projection games (Rao 2008; also Dinur–Steurer 2014 analytic approach), imported as a known result. The bound (1−g2/16)n(1-g^2/16)^n matches Rao's form.

Uses

Nothing else in the paper

Used by

thmThe Unique Games TheoremlemAdvice agreement decays with clean coordinatesclaimAlphabet-independent gap fixes repetition exponentclaimYES and NO values of the final gameclaimConditional agreement bounded by repeated 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.1 Classical projection-game repetition
Page
—
Label
thm:repetition
Line
sections/05-clean.tex:26
Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

  • info
    structure_uncertain
    No proof in paper; it is Dinur–Steurer Corollary 1.2.