Parallel repetition causes fast decay in multi player xor games
Parallel Repetition for k-Player XOR Games
Computational Complexity
Summary
This paper studies multiplayer XOR games, where several players try to satisfy a mathematical condition by providing answers based on separate challenges. The authors show that when repeating these games many times in parallel, the chance of winning all rounds drops exponentially if the players cannot win perfectly. They use a new approach that links the original game to a related game easier to analyze with known techniques, leading to a clear proof that the winning probability decays quickly as the number of repetitions grows.
What this means in practice
- •For cryptography engineers: Design secure protocols by understanding how repeating XOR-based challenges reduces the chance of cheating.
- •For complexity theory tool builders: Use the paper’s methods to certify hardness results for certain computational problems involving multiplayer interactive proofs.
A theory result. No direct application yet.
Authors
Mark Braverman, Dor Minzer
Abstract
In a $k$-XOR game $Ψ$ over $\mathbb{F}_p$, a verifier samples challenges $(x_1,\ldots,x_k)\simμ$ where $μ$ is a distribution over $Σ_1\times\ldots\times Σ_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 Σ_1\times\ldots\times Σ_k\to\mathbb{F}_p$ is a fixed map. We show that if $Ψ$ has value strictly less than $1$, then the value of the $n$-fold repeated game $Ψ^{\otimes n}$ is at most $2^{-cn}$ where $c = c(Ψ)>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 $Ψ$ with value strictly less than $1$ to a $2k$-player game $Ψ'$ with commuting value less than $1$, such that $\mathsf{val}(Ψ^{\otimes n})\leq \mathsf{val}((Ψ')^{\otimes n})$. We prove that $\mathsf{val}(Ψ')<1$ has a direct proof using nothing more than the Cauchy-Schwarz inequality, which we are able to tensorize to get that $\mathsf{val}((Ψ')^{\otimes n})$ vanishes exponentially fast in $n$.