Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-285 | 21st October 2026 22:54

Parallel Repetition for k-Player XOR Games

RSS-Feed




TR26-285
Authors: Mark Braverman, Dor Minzer
Publication: 29th October 2026 01:53
Downloads: 18
Keywords: 


Abstract:

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$.



ISSN 1433-8092 | Imprint