Source-linked AI summary
Parallel Repetition for k-Player XOR Games
Mark Braverman, Dor Minzer
TL;DR
The paper addresses how to amplify the soundness gap when a game has value below one. It transforms k-XOR games into 2k-player games and uses commuting embeddings and tensorized Cauchy–Schwarz to prove exponential decay under repetition.
Problem
For a game Ψ with val(Ψ) < 1, the parallel repetition conjecture asks whether val(Ψ⊗n) decays exponentially in n.
Source: §1 · p. 2Method
The paper transforms Ψ into a 2k-player game Ψ′ with no commuting embedding and applies a Cauchy–Schwarz proof that tensorizes.
Source: §1.3.2 · p. 6, §1.3.3 · p. 7Results
For every k-XOR game Ψ with val(Ψ) < 1, val(Ψ⊗n) ≤ (1−ε)^n for some ε = ε(Ψ) > 0.
Source: §1.2 · p. 4Takeaways & Limitations
The result covers k-XOR games for all k ≥ 2 without assumptions on the question distribution μ.
Source: §1.2 · p. 4The direct Cauchy–Schwarz plan fails for some games without Abelian embeddings, where the direct-sum statement can fail.
Source: §1.3.2 · p. 6
Abstract
from arXiv · showhide
In a $k$-XOR game $\Psi$ over $\mathbb{F}_p$, a verifier samples challenges $(x_1,\ldots,x_k)\sim\mu$ where $\mu$ is a distribution over $\Sigma_1\times\ldots\times \Sigma_k$, sends $x_i$ to player $i$ and receives an answer $f_i(x_i)\in\mathbb{F}_p$, and accepts if and only if $f_1(x_1)+\ldots+f_k(x_k)=t(x_1,\ldots,x_k)$, where $t\colon \Sigma_1\times\ldots\times \Sigma_k\to\mathbb{F}_p$ is a fixed map. We show that if $\Psi$ has value strictly less than $1$, then the value of the $n$-fold repeated game $\Psi^{\otimes n}$ is at most $2^{-cn}$ where $c = c(\Psi)>0$ is a fixed constant. This extends a previous result of [Bhangale-Braverman-Khot-Liu-Minzer] showing exponential decay for some $3$-XOR games. Our proof uses a relaxation of the value of games studied in the quantum setting, called the commuting value of a game. We show a transformation that maps a $k$-player game $\Psi$ with value strictly less than $1$ to a $2k$-player game $\Psi'$ with commuting value less than $1$, such that $\mathsf{val}(\Psi^{\otimes n})\leq \mathsf{val}((\Psi')^{\otimes n})$. We prove that $\mathsf{val}(\Psi')<1$ has a direct proof using nothing more than the Cauchy-Schwarz inequality, which we are able to tensorize to get that $\mathsf{val}((\Psi')^{\otimes n})$ vanishes exponentially fast in $n$.
1 Introduction
The paper proves exponential parallel-repetition decay for every k-XOR game of value below one, using a transformed game and a commuting-embedding/Cauchy–Schwarz proof strategy.
1.1 Prior Work
- Earlier exponential-decay results covered general 2-player games and selected multi-player classes, while general k-player games were only known to have value tending to zero.The cited prior results include connected games, GHZ-related games, and other restricted classes.Source: §1.1 · p. 2
1.2 Our Results
- For every k-XOR game Ψ with val(Ψ) < 1, val(Ψ⊗n) ≤ (1−ε)^n for some ε = ε(Ψ) > 0.The theorem applies for all n.Source: §1.2 · p. 4
- The theorem applies to k-XOR games for all k ≥ 2 without restrictions on μ, and extends to games over any finite Abelian group.The earlier result [7] was limited to k = 3 and required no (Z, +) embedding.Source: §1.2 · p. 4
1.3.1 The Previous Approach to XOR Games
- Prior [7] proofs split on Abelian embeddings, using additive combinatorics for embedded games and tensorization for games without them.The paper notes that the GHZ game falls in the Abelian-embedding case.Source: §1.3.1 · p. 4
1.3.2 Our Approach
- The BLR trick reduces a k-XOR game with an Abelian embedding to an XOR game without one.This supplies a route for addressing games whose initial structure falls into the Abelian-embedding case.Source: §1.3.2 · p. 5
- The transformation creates a 2k-player game with paired players receiving F_p-offset questions, while preserving val(Ψ⊗n) ≤ val((Ψ′)⊗n).The question to player i is (x_i, α_i), and to player i′ it is (x_i, α_i + γ).Source: §1.3.2 · p. 6
- The direct Cauchy–Schwarz plan fails for some games without Abelian embeddings, where the proposed direct-sum statement can fail.This failure motivates a different approach to the proof.Source: §1.3.2 · p. 6
1.3.3 Commuting Embeddings
- The transformed game has no commuting embedding, which leads to structured contradictions handled by Cauchy–Schwarz and tensorized to prove exponential decay.The paper contrasts its Cauchy–Schwarz approach with prior additive-combinatorics proofs for GHZ and 3-XOR games.Source: §1.2 · p. 4, §1.3.3 · p. 7
2 On the BLR-trick, Commuting Embeddings and Ordered Contradictions
The section uses the BLR-trick to connect failure of commuting embeddings with structured contradictions. It characterizes that structure as an ordered contradiction and constructs commuting embeddings when none exists.
2.2 From No Commuting Embeddings to Ordered Contradictions
- An ordered contradiction is a signed collection of constraints whose right-hand sides conflict while each player's left-hand-side word cancels combinatorially.The section introduces generalized games to allow the same left-hand side with different right-hand sides.Source: §2.2 · p. 9
- Lemma 2.3 characterizes generalized k-XOR games without commuting embeddings exactly as games with an ordered contradiction.The paper gives a direct proof, generalizing the argument for F2 in [4, Theorem 2.1], of a result following from [5, Theorem 5.10].Source: §2.2 · p. 9
- When no ordered contradiction exists, the proof constructs commuting embeddings using operators on equivalence classes of expressions.The construction uses a Hilbert space with basis indexed by equivalence classes; the resulting operators are unitary and commute.Source: §2.2 · p. 10
3 From Ordered Contradictions to Cauchy-Schwarz Proofs
The section converts ordered contradictions into Cauchy–Schwarz proofs that a game's value is below one. Gluing reduces the contradiction's reading-sequence measure, and tensorization yields exponential decay in the number of nonzero coordinates.
3.1 The Gluing Operation
- Gluing over a nonempty player set preserves perfect value and, by one Cauchy–Schwarz application, transfers a value-below-one bound from the glued game to the original.The glued verifier samples a second challenge conditioned on matching the first challenge on the glued players.Source: §3.1 · pp. 10–11
3.2 Realizing Ordered Contradictions via Gluing
- For any ordered contradiction, one can choose players to glue so the contradiction persists while its maximal reading-sequence measure strictly decreases.The reading sequences track the number of uncancelled symbols as each player's word is read.Source: §3.2 · p. 11
- Repeated gluing terminates with a player-free game containing two challenges with different right-hand sides.The process preserves an ordered contradiction of the original length at every step.Source: §3.2 · pp. 12–13
3.3 Tensorization
- For an ordered contradiction of length N, tensorization bounds the relevant correlation by (1 − ε)^d for some ε > 0, when at least d coordinates have nonzero coefficients.The proof iterates the gluing inequality and obtains a decay bound from the terminal player-free game.Source: §3.3 · p. 13
4 Proof of Theorem 1.3
The proof applies the ordered-contradiction and tensorization results to the transformed game Ψ′. Its repeated-game value decays exponentially, and a strategy-transfer inequality carries that bound to Ψ.
4 Proof of Theorem 1.3
- The transformed game Ψ′ has no commuting embeddings and therefore has an ordered contradiction.This lets the proof invoke the ordered-contradiction tensorization bound.Source: §4 · p. 14
- For some ε = ε(Ψ) > 0, val((Ψ′)^⊗n) ≤ (1 − ε)^n for every n.The proof establishes the bound for any strategy in the repeated transformed game.Source: §4 · p. 14
- The repeated value of Ψ is at most that of Ψ′: val(Ψ^⊗n) ≤ val((Ψ′)^⊗n).The proof constructs strategies for the transformed game from any strategy for Ψ^⊗n.Source: §4 · p. 14
A An example: the Levi–Civita game
The appendix illustrates iterative gluing on the Levi–Civita game. The example tracks how the maximal reading sequence decreases while the signed target sum remains nonzero.
A An example: the Levi–Civita game
- The Levi–Civita game has an ordered contradiction formed from six challenges and signs, with signed target sum 1 in F2.The players' words reduce to the empty word, and the maximal reading sequence is h3.Source: A An example: the Levi–Civita game · p. 18
- In the first gluing, the pairing is (1, 6), (2, 5), (3, 4), and the maximal sequence is h = 0123210.The resulting reading sequences for the four players are each strictly smaller than h.Source: A An example: the Levi–Civita game · p. 18
- After four gluings, two rows have the same question tuple but targets 0 and 1; the final gluing leaves no players and targets (0, 0, 0, 0, 0, 1).At every step, the maximal reading sequence decreases and the signed target sum remains 1.Source: A An example: the Levi–Civita game · p. 18