Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2204.00858

Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs

Uma Girish, Mittal, Kunal, Ran Raz, Zhan, Wei

Published Apr 2, 2022• 0 citations
arXivHTMLPDF

Abstract

We prove that for every 3-player (3-prover) game $\mathcal G$ with value less than one, whose query distribution has the support $\mathcal S = \{(1,0,0), (0,1,0), (0,0,1)\}$ of hamming weight one vectors, the value of the $n$-fold parallel repetition $\mathcal G^{\otimes n}$ decays polynomially fast to zero; that is, there is a constant $c = c(\mathcal G)>0$ such that the value of the game $\mathcal G^{\otimes n}$ is at most $n^{-c}$. Following the recent work of Girish, Holmgren, Mittal, Raz and Zhan (STOC 2022), our result is the missing piece that implies a similar bound for a much more general class of multiplayer games: For $\textbf{every}$ 3-player game $\mathcal G$ over $\textit{binary questions}$ and $\textit{arbitrary answer lengths}$, with value less than 1, there is a constant $c = c(\mathcal G)>0$ such that the value of the game $\mathcal G^{\otimes n}$ is at most $n^{-c}$. Our proof technique is new and requires many new ideas. For example, we make use of the Level-$k$ inequalities from Boolean Fourier Analysis, which, to the best of our knowledge, have not been explored in this context prior to our work.

DOI
10.48550/arxiv.2204.00858

Related papers

Parallel repetition for all 3-player games over binary alphabet

Uma Girish, Justin Holmgren, Kunal Mittal +2 more

We prove that for every 3-player (3-prover) game, with binary questions and answers and value <1, the value of the n-fold parallel repetition of the game decays polynomially fast to 0. That is, for every such game, there exists a constant c>0, such that the value of the n-fold parallel repetition of the game is at most n−c.

arXiv:2202.06826•ACM Symposium on Theory of Computing (STOC)•Jun 9, 2022•6 citations

Parallel Repetition for the GHZ Game: A Simpler Proof

Uma Girish, Justin Holmgren, Mittal, Kunal +2 more

We give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly. That is, we show that the value of the $n$-fold GHZ game is at most $n^{-Ω(1)}$. This was first established by Holmgren and Raz [HR20]. We present a new proof of this theorem that we believe to be simpler and more direct. Unlike most previous works on parallel repetition, our proof makes no use of information theory, and relies on the use of Fourier analysis. The GHZ game [GHZ89] has played a foundational role in the understanding of quantum information theory, due in part to the fact that quantum strategies can win the GHZ game with probability 1. It is possible that improved parallel repetition bounds may find applications in this setting. Recently, Dinur, Harsha, Venkat, and Yuen [DHVY17] highlighted the GHZ game as a simple three-player game, which is in some sense maximally far from the class of multi-player games whose behavior under parallel repetition is well understood. Dinur et al. conjectured that parallel repetition decreases the value of the GHZ game exponentially quickly, and speculated that progress on proving this would shed light on parallel repetition for general multi-player (multi-prover) games.

arXiv:2107.06156•Jul 13, 2021•0 citations

Parallel Repetition for the GHZ Game: A Simpler Proof

Uma Girish, Justin Holmgren, Mittal, Kunal +2 more

We give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly. That is, we show that the value of the n-fold GHZ game is at most n^{-Ω(1)}. This was first established by Holmgren and Raz [Holmgren and Raz, 2020]. We present a new proof of this theorem that we believe to be simpler and more direct. Unlike most previous works on parallel repetition, our proof makes no use of information theory, and relies on the use of Fourier analysis. The GHZ game [Greenberger et al., 1989] has played a foundational role in the understanding of quantum information theory, due in part to the fact that quantum strategies can win the GHZ game with probability 1. It is possible that improved parallel repetition bounds may find applications in this setting. Recently, Dinur, Harsha, Venkat, and Yuen [Dinur et al., 2017] highlighted the GHZ game as a simple three-player game, which is in some sense maximally far from the class of multi-player games whose behavior under parallel repetition is well understood. Dinur et al. conjectured that parallel repetition decreases the value of the GHZ game exponentially quickly, and speculated that progress on proving this would shed light on parallel repetition for general multi-player (multi-prover) games.

Leibniz international proceedings in informatics•Jan 1, 2021•1 citation

Improved Parallel Repetition for GHZ-Supported Games via Spreadness

Yang P. Liu, Shachar Lovett, Kunal Mittal

We prove that for any 3-player game $\mathcal G$, whose query distribution has the same support as the GHZ game (i.e., all $x,y,z\in \{0,1\}$ satisfying $x+y+z=0\pmod{2}$), the value of the $n$-fold parallel repetition of $\mathcal G$ decays exponentially fast: \[ \text{val}(\mathcal G^{\otimes n}) \leq \exp(-n^c)\] for all sufficiently large $n$, where $c>0$ is an absolute constant. We also prove a concentration bound for the parallel repetition of the GHZ game: For any constant $ε>0$, the probability that the players win at least a $\left(\frac{3}{4}+ε\right)$ fraction of the $n$ coordinates is at most $\exp(-n^c)$, where $c=c(ε)>0$ is a constant. In both settings, our work exponentially improves upon the previous best known bounds which were only polynomially small, i.e., of the order $n^{-Ω(1)}$. Our key technical tool is the notion of \emph{algebraic spreadness} adapted from the breakthrough work of Kelley and Meka (FOCS '23) on sets free of 3-term progressions.

arXiv:2602.09290•Feb 10, 2026•0 citations

Improved Parallel Repetition for GHZ-Supported Games via Spreadness

Yang P. Liu, Shachar Lovett, Mittal, Kunal

We prove that for any 3-player game G, whose query distribution has the same support as the GHZ game (i.e., all x,y,z ∈ {0,1} satisfying x+y+z = 0 (mod 2)), the value of the n-fold parallel repetition of G decays exponentially fast: val(G^{⊗ n}) ≤ exp(-n^c) for all sufficiently large n, where c > 0 is an absolute constant. We also prove a concentration bound for the parallel repetition of the GHZ game: For any constant ε > 0, the probability that the players win at least a (3/4+ε) fraction of the n coordinates is at most exp(-n^c), where c = c(ε) > 0 is a constant. In both settings, our work exponentially improves upon the previous best known bounds which were only polynomially small, i.e., of the order n^{-Ω(1)}. Our key technical tool is the notion of algebraic spreadness adapted from the breakthrough work of Kelley and Meka (FOCS '23) on sets free of 3-term progressions.

Leibniz international proceedings in informatics•Jan 1, 2026•0 citations

Parallel Repetition for k-Player XOR Games

Mark Braverman, Dor Minzer

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

arXiv:2610.30455•Oct 21, 2026•0 citations
We prove that for every 3-player (3-prover) game G\mathcal GG with value less than one, whose query distribution has the support S={(1,0,0),(0,1,0),(0,0,1)}\mathcal S = \{(1,0,0), (0,1,0), (0,0,1)\}S={(1,0,0),(0,1,0),(0,0,1)} of hamming weight one vectors, the value of the nnn-fold parallel repetition G⊗n\mathcal G^{\otimes n}G⊗n decays polynomially fast to zero; that is, there is a constant c=c(G)>0c = c(\mathcal G)>0c=c(G)>0 such that the value of the game G⊗n\mathcal G^{\otimes n}G⊗n is at most n−cn^{-c}n−c. Following the recent work of Girish, Holmgren, Mittal, Raz and Zhan (STOC 2022), our result is the missing piece that implies a similar bound for a much more general class of multiplayer games: For every\textbf{every}every 3-player game G\mathcal GG over binary questions\textit{binary questions}binary questions and arbitrary answer lengths\textit{arbitrary answer lengths}arbitrary answer lengths, with value less than 1, there is a constant c=c(G)>0c = c(\mathcal G)>0c=c(G)>0 such that the value of the game G⊗n\mathcal G^{\otimes n}G⊗n is at most n−cn^{-c}n−c. Our proof technique is new and requires many new ideas. For example, we make use of the Level-kkk inequalities from Boolean Fourier Analysis, which, to the best of our knowledge, have not been explored in this context prior to our work.
We give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly. That is, we show that the value of the nnn-fold GHZ game is at most n−Ω(1)n^{-Ω(1)}n−Ω(1). This was first established by Holmgren and Raz [HR20]. We present a new proof of this theorem that we believe to be simpler and more direct. Unlike most previous works on parallel repetition, our proof makes no use of information theory, and relies on the use of Fourier analysis. The GHZ game [GHZ89] has played a foundational role in the understanding of quantum information theory, due in part to the fact that quantum strategies can win the GHZ game with probability 1. It is possible that improved parallel repetition bounds may find applications in this setting. Recently, Dinur, Harsha, Venkat, and Yuen [DHVY17] highlighted the GHZ game as a simple three-player game, which is in some sense maximally far from the class of multi-player games whose behavior under parallel repetition is well understood. Dinur et al. conjectured that parallel repetition decreases the value of the GHZ game exponentially quickly, and speculated that progress on proving this would shed light on parallel repetition for general multi-player (multi-prover) games.
We give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly. That is, we show that the value of the n-fold GHZ game is at most n^{-Ω(1)}. This was first established by Holmgren and Raz [Holmgren and Raz, 2020]. We present a new proof of this theorem that we believe to be simpler and more direct. Unlike most previous works on parallel repetition, our proof makes no use of information theory, and relies on the use of Fourier analysis. The GHZ game [Greenberger et al., 1989] has played a foundational role in the understanding of quantum information theory, due in part to the fact that quantum strategies can win the GHZ game with probability 1. It is possible that improved parallel repetition bounds may find applications in this setting. Recently, Dinur, Harsha, Venkat, and Yuen [Dinur et al., 2017] highlighted the GHZ game as a simple three-player game, which is in some sense maximally far from the class of multi-player games whose behavior under parallel repetition is well understood. Dinur et al. conjectured that parallel repetition decreases the value of the GHZ game exponentially quickly, and speculated that progress on proving this would shed light on parallel repetition for general multi-player (multi-prover) games.
We prove that for any 3-player game G\mathcal GG, whose query distribution has the same support as the GHZ game (i.e., all x,y,z∈{0,1}x,y,z\in \{0,1\}x,y,z∈{0,1} satisfying x+y+z=0(mod2)x+y+z=0\pmod{2}x+y+z=0(mod2)), the value of the nnn-fold parallel repetition of G\mathcal GG decays exponentially fast: val(G⊗n)≤exp⁡(−nc) \text{val}(\mathcal G^{\otimes n}) \leq \exp(-n^c)val(G⊗n)≤exp(−nc) for all sufficiently large nnn, where c>0c>0c>0 is an absolute constant. We also prove a concentration bound for the parallel repetition of the GHZ game: For any constant ε>0ε>0ε>0, the probability that the players win at least a (34+ε)\left(\frac{3}{4}+ε\right)(43​+ε) fraction of the nnn coordinates is at most exp⁡(−nc)\exp(-n^c)exp(−nc), where c=c(ε)>0c=c(ε)>0c=c(ε)>0 is a constant. In both settings, our work exponentially improves upon the previous best known bounds which were only polynomially small, i.e., of the order n−Ω(1)n^{-Ω(1)}n−Ω(1). Our key technical tool is the notion of \emph{algebraic spreadness} adapted from the breakthrough work of Kelley and Meka (FOCS '23) on sets free of 3-term progressions.
We prove that for any 3-player game G, whose query distribution has the same support as the GHZ game (i.e., all x,y,z ∈ {0,1} satisfying x+y+z = 0 (mod 2)), the value of the n-fold parallel repetition of G decays exponentially fast: val(G^{⊗ n}) ≤ exp(-n^c) for all sufficiently large n, where c > 0 is an absolute constant. We also prove a concentration bound for the parallel repetition of the GHZ game: For any constant ε > 0, the probability that the players win at least a (3/4+ε) fraction of the n coordinates is at most exp(-n^c), where c = c(ε) > 0 is a constant. In both settings, our work exponentially improves upon the previous best known bounds which were only polynomially small, i.e., of the order n^{-Ω(1)}. Our key technical tool is the notion of algebraic spreadness adapted from the breakthrough work of Kelley and Meka (FOCS '23) on sets free of 3-term progressions.
In a kkk-XOR game ΨΨΨ over Fp\mathbb{F}_pFp​, a verifier samples challenges (x1,…,xk)∼μ(x_1,\ldots,x_k)\simμ(x1​,…,xk​)∼μ where μμμ is a distribution over Σ1×…×ΣkΣ_1\times\ldots\times Σ_kΣ1​×…×Σk​, sends xix_ixi​ to player iii and receives an answer fi(xi)∈Fpf_i(x_i)\in\mathbb{F}_pfi​(xi​)∈Fp​, and accepts if and only if f1(x1)+…+fk(xk)=t(x1,…,xk)f_1(x_1)+\ldots+f_k(x_k)=t(x_1,\ldots,x_k)f1​(x1​)+…+fk​(xk​)=t(x1​,…,xk​), where t ⁣:Σ1×…×Σk→Fpt\colon Σ_1\times\ldots\times Σ_k\to\mathbb{F}_pt:Σ1​×…×Σk​→Fp​ is a fixed map. We show that if ΨΨΨ has value strictly less than 111, then the value of the nnn-fold repeated game Ψ⊗nΨ^{\otimes n}Ψ⊗n is at most 2−cn2^{-cn}2−cn where c=c(Ψ)>0c = c(Ψ)>0c=c(Ψ)>0 is a fixed constant. This extends a previous result of [Bhangale-Braverman-Khot-Liu-Minzer] showing exponential decay for some 333-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 kkk-player game ΨΨΨ with value strictly less than 111 to a 2k2k2k-player game Ψ′Ψ'Ψ′ with commuting value less than 111, such that val(Ψ⊗n)≤val((Ψ′)⊗n)\mathsf{val}(Ψ^{\otimes n})\leq \mathsf{val}((Ψ')^{\otimes n})val(Ψ⊗n)≤val((Ψ′)⊗n). We prove that val(Ψ′)<1\mathsf{val}(Ψ')<1val(Ψ′)<1 has a direct proof using nothing more than the Cauchy-Schwarz inequality, which we are able to tensorize to get that val((Ψ′)⊗n)\mathsf{val}((Ψ')^{\otimes n})val((Ψ′)⊗n) vanishes exponentially fast in nnn.