Parallel Repetition for $3$-Player XOR Games

Abstract

In a $3$-$\mathsf{XOR}$ game $\mathcal{G}$, the verifier samples a challenge $(x,y,z)\sim \hat{I}¼$ where $\hat{I}¼$ is a probability distribution over $\hat{I}\pounds \times \hat{I}“\times \hat{I}¦$, and a map $t:\hat{I}\pounds \times \hat{I}“\times \hat{I}¦\to \mathcal{A}$ for a finite Abelian group $\mathcal{A}$ defining a constraint. The verifier sends the questions $x$, $y$ and $z$ to the players Alice, Bob and Charlie respectively, receives answers $f(x)$, $g(y)$ and $h(z)$ that are elements in $\mathcal{A}$ and accepts if $f(x)+g(y)+h(z)=t(x,y,z)$. The value, $\mathsf{val}(\mathcal{G})$, of the game is defined to be the maximum probability the verifier accepts over all players' strategies. We show that if $\mathcal{G}$ is a $3$-$\mathsf{XOR}$ game with value strictly less than $1$, whose underlying distribution over questions $\hat{I}¼$ does not admit Abelian embeddings into $(\mathbb{Z},+)$, then the value of the $n$-fold repetition of $\mathcal{G}$ is exponentially decaying. That is, there exists $c=c(\mathcal{G})>0$ such that $\mathsf{val}({\mathcal{G}}^{\otimes n})\le 2^{-cn}$. This extends a previous result of [Braverman-Khot-Minzer, FOCS 2023] showing exponential decay for the GHZ game. Our proof combines tools from additive combinatorics and tools from discrete Fourier analysis.