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

Leibniz international proceedings in informatics

Multiplayer Parallel Repetition for Expanding Games

Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen

Published Jan 1, 2017• 5 citations
Publisher

Abstract

We investigate the value of parallel repetition of one-round games with any number of players k>=2. It has been an open question whether an analogue of Raz's Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially with the number of repetitions. Verbitsky has shown, via a reduction to the density Hales-Jewett theorem, that the value of the repeated game must approach zero, as the number of repetitions increases. However, the rate of decay obtained in this way is extremely slow, and it is an open question whether the true rate is exponential as is the case for all two-player games. Exponential decay bounds are known for several special cases of multi-player games, e.g., free games and anchored games. In this work, we identify a certain expansion property of the base game and show all games with this property satisfy an exponential decay parallel repetition bound. Free games and anchored games satisfy this expansion property, and thus our parallel repetition theorem reproduces all earlier exponential-decay bounds for multiplayer games. More generally, our parallel repetition bound applies to all multiplayer games that are *connected* in a certain sense. We also describe a very simple game, called the GHZ game, that does not satisfy this connectivity property, and for which we do not know an exponential decay bound. We suspect that progress on bounding the value of this the parallel repetition of the GHZ game will lead to further progress on the general question.

DOI
10.4230/lipics.itcs.2017.37

Related papers

Multiplayer parallel repetition for expander games

Irit Dinur, Prahladh Harsha, Rakesh Venkat +1 more

We investigate the value of parallel repetition of one-round games with any number of players $k\ge 2$. It has been an open question whether an analogue of Raz's Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially with the number of repetitions. Verbitsky has shown, via a reduction to the density Hales-Jewett theorem, that the value of the repeated game must approach zero, as the number of repetitions increases. However, the rate of decay obtained in this way is extremely slow, and it is an open question whether the true rate is exponential as is the case for all two-player games. Exponential decay bounds are known for several special cases of multi-player games, e.g., free games and anchored games. In this work, we identify a certain expansion property of the base game and show all games with this property satisfy an exponential decay parallel repetition bound. Free games and anchored games satisfy this expansion property, and thus our parallel repetition theorem reproduces all earlier exponential-decay bounds for multiplayer games. More generally, our parallel repetition bound applies to all multiplayer games that are connected in a certain sense. We also describe a very simple game, called the GHZ game, that does not satisfy this connectivity property, and for which we do not know an exponential decay bound. We suspect that progress on bounding the value of this the parallel repetition of the GHZ game will lead to further progress on the general question.

arXiv:1610.08349•Electronic colloquium on computational complexity•Oct 26, 2016•4 citations

Anchoring games for parallel repetition

Mohammad Bavarian, Thomas Vidick, Henry Yuen

Two major open problems regarding the parallel repetition of games are whether an analogue of Raz's parallel-repetition theorem holds for (a) games with more than two players, and (b) games with quantum players using entanglement. We make progress on both problems: we introduce a class of games we call anchored, and prove exponential-decay parallel repetition theorems for anchored games in the multiplayer and entangled-player settings. We introduce a simple transformation on games called anchoring and show that this transformation turns any game into an anchored game. Together, our parallel repetition theorem and our anchoring transformation provide a simple and efficient hardness-amplification technique in both the classical multiplayer and quantum settings.

•Sep 24, 2015•10 citations

Hardness amplification for entangled games via anchoring

Mohammad Bavarian, Thomas Vidick, Henry Yuen

We study the parallel repetition of one-round games involving players that can use quantum entanglement. A major open question in this area is whether parallel repetition reduces the entangled value of a game at an exponential rate - in other words, does an analogue of Raz's parallel repetition theorem hold for games with players sharing quantum entanglement? Previous results only apply to special classes of games.

ACM Symposium on Theory of Computing (STOC)•Jun 15, 2017•19 citations

A Parallel Repetition Theorem for the GHZ Game

Justin Holmgren, Ran Raz

We prove that parallel repetition of the (3-player) GHZ game reduces the value of the game polynomially fast to 0. That is, the value of the GHZ game repeated in parallel $t$ times is at most $t^{-Ω(1)}$. Previously, only a bound of $\approx \frac{1}{α(t)}$, where $α$ is the inverse Ackermann function, was known. The GHZ game was recently identified by Dinur, Harsha, Venkat and Yuen as a multi-player game where all existing techniques for proving strong bounds on the value of the parallel repetition of the game fail. Indeed, to prove our result we use a completely new proof technique. Dinur, Harsha, Venkat and Yuen speculated that progress on bounding the value of the parallel repetition of the GHZ game may lead to further progress on the general question of parallel repetition of multi-player games. They suggested that the strong correlations present in the GHZ question distribution represent the "hardest instance" of the multi-player parallel repetition problem. Another motivation for studying the parallel repetition of the GHZ game comes from the field of quantum information. The GHZ game, first introduced by Greenberger, Horne and Zeilinger, is a central game in the study of quantum entanglement and has been studied in numerous works. For example, it is used for testing quantum entanglement and for device-independent quantum cryptography. In such applications a game is typically repeated to reduce the probability of error, and hence bounds on the value of the parallel repetition of the game may be useful.

arXiv:2008.05059•Aug 12, 2020•3 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

Multiplayer parallel repetition without dependency-breaking and anchoring variables: monotonic, concave amplification

Pete Rigas

We obtain quantitative estimates on the decay of the multiplayer optimal value under parallel repetition. In comparison to a previous work of the author in 2025 (arXiv: 2508.09380) which sought to generalize dependency-breaking and anchoring variables from two-player Quantum games, being able to establish quantitative estimates on the decay of the optimal value of a multiplayer game under parallel repetition is of interest to establish under different assumptions. Specifically, independently of the dependency-breaking and anchoring variables that have previously been employed to remove correlations from entangled information shared between Alice and Bob (hence removing dependencies), monotonic concave functions can be used in place of such variables to obtain rates of decay on the optimal value. The game-theoretic setting with two players was first analyzed with monotonic concave functions by Lanzenberger and Maurer. For $q_i , x_i > 0$ $\forall 1 \leq i \leq N$ where $N > 0 $ is the total number of players we adddress an open question raised in their work regarding potential generalizations of two-player monotonic concave functions, through amplification functions of the form $Ψ_{\textit{Mult}} \equiv Ψ= N - \underset{1 \leq i \leq N}{\prod} \mathrm{exp} \big[ - q_i x_i \big]$, which in the multiplayer game-theoretic setting have more intricate combinatorial structures.

quant-pharXiv:2605.08259•May 11, 2026•0 citations
We investigate the value of parallel repetition of one-round games with any number of players k>=2. It has been an open question whether an analogue of Raz's Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially with the number of repetitions. Verbitsky has shown, via a reduction to the density Hales-Jewett theorem, that the value of the repeated game must approach zero, as the number of repetitions increases. However, the rate of decay obtained in this way is extremely slow, and it is an open question whether the true rate is exponential as is the case for all two-player games. Exponential decay bounds are known for several special cases of multi-player games, e.g., free games and anchored games. In this work, we identify a certain expansion property of the base game and show all games with this property satisfy an exponential decay parallel repetition bound. Free games and anchored games satisfy this expansion property, and thus our parallel repetition theorem reproduces all earlier exponential-decay bounds for multiplayer games. More generally, our parallel repetition bound applies to all multiplayer games that are connected in a certain sense. We also describe a very simple game, called the GHZ game, that does not satisfy this connectivity property, and for which we do not know an exponential decay bound. We suspect that progress on bounding the value of this the parallel repetition of the GHZ game will lead to further progress on the general question.
We investigate the value of parallel repetition of one-round games with any number of players k≥2k\ge 2k≥2. It has been an open question whether an analogue of Raz's Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially with the number of repetitions. Verbitsky has shown, via a reduction to the density Hales-Jewett theorem, that the value of the repeated game must approach zero, as the number of repetitions increases. However, the rate of decay obtained in this way is extremely slow, and it is an open question whether the true rate is exponential as is the case for all two-player games. Exponential decay bounds are known for several special cases of multi-player games, e.g., free games and anchored games. In this work, we identify a certain expansion property of the base game and show all games with this property satisfy an exponential decay parallel repetition bound. Free games and anchored games satisfy this expansion property, and thus our parallel repetition theorem reproduces all earlier exponential-decay bounds for multiplayer games. More generally, our parallel repetition bound applies to all multiplayer games that are connected in a certain sense. We also describe a very simple game, called the GHZ game, that does not satisfy this connectivity property, and for which we do not know an exponential decay bound. We suspect that progress on bounding the value of this the parallel repetition of the GHZ game will lead to further progress on the general question.
Two major open problems regarding the parallel repetition of games are whether an analogue of Raz's parallel-repetition theorem holds for (a) games with more than two players, and (b) games with quantum players using entanglement. We make progress on both problems: we introduce a class of games we call anchored, and prove exponential-decay parallel repetition theorems for anchored games in the multiplayer and entangled-player settings. We introduce a simple transformation on games called anchoring and show that this transformation turns any game into an anchored game. Together, our parallel repetition theorem and our anchoring transformation provide a simple and efficient hardness-amplification technique in both the classical multiplayer and quantum settings.
We prove that parallel repetition of the (3-player) GHZ game reduces the value of the game polynomially fast to 0. That is, the value of the GHZ game repeated in parallel ttt times is at most t−Ω(1)t^{-Ω(1)}t−Ω(1). Previously, only a bound of ≈1α(t)\approx \frac{1}{α(t)}≈α(t)1​, where ααα is the inverse Ackermann function, was known. The GHZ game was recently identified by Dinur, Harsha, Venkat and Yuen as a multi-player game where all existing techniques for proving strong bounds on the value of the parallel repetition of the game fail. Indeed, to prove our result we use a completely new proof technique. Dinur, Harsha, Venkat and Yuen speculated that progress on bounding the value of the parallel repetition of the GHZ game may lead to further progress on the general question of parallel repetition of multi-player games. They suggested that the strong correlations present in the GHZ question distribution represent the "hardest instance" of the multi-player parallel repetition problem. Another motivation for studying the parallel repetition of the GHZ game comes from the field of quantum information. The GHZ game, first introduced by Greenberger, Horne and Zeilinger, is a central game in the study of quantum entanglement and has been studied in numerous works. For example, it is used for testing quantum entanglement and for device-independent quantum cryptography. In such applications a game is typically repeated to reduce the probability of error, and hence bounds on the value of the parallel repetition of the game may be useful.
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 obtain quantitative estimates on the decay of the multiplayer optimal value under parallel repetition. In comparison to a previous work of the author in 2025 (arXiv: 2508.09380) which sought to generalize dependency-breaking and anchoring variables from two-player Quantum games, being able to establish quantitative estimates on the decay of the optimal value of a multiplayer game under parallel repetition is of interest to establish under different assumptions. Specifically, independently of the dependency-breaking and anchoring variables that have previously been employed to remove correlations from entangled information shared between Alice and Bob (hence removing dependencies), monotonic concave functions can be used in place of such variables to obtain rates of decay on the optimal value. The game-theoretic setting with two players was first analyzed with monotonic concave functions by Lanzenberger and Maurer. For qi,xi>0q_i , x_i > 0qi​,xi​>0 ∀1≤i≤N\forall 1 \leq i \leq N∀1≤i≤N where $N > 0 $ is the total number of players we adddress an open question raised in their work regarding potential generalizations of two-player monotonic concave functions, through amplification functions of the form ΨMult≡Ψ=N−∏1≤i≤Nexp[−qixi]Ψ_{\textit{Mult}} \equiv Ψ= N - \underset{1 \leq i \leq N}{\prod} \mathrm{exp} \big[ - q_i x_i \big]ΨMult​≡Ψ=N−1≤i≤N∏​exp[−qi​xi​], which in the multiplayer game-theoretic setting have more intricate combinatorial structures.