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

Annual Symposium on Foundations of Computer Science

A Counterexample to Strong Parallel Repetition

Ran Raz

Published Oct 1, 2008• 82 citations
Publisher

Abstract

The parallel repetition theorem states that, for any two-prover game with value $1-\epsilon$ (for, say, $\epsilon\leq1/2$), the value of the game repeated in parallel n times is at most $(1-\epsilon^c)^{\Omega(n/s)}$, where s is the answer's length (of the original game) and c is a universal constant [R. Raz, SIAM J. Comput., 27 (1998), pp. 763–803]. Several researchers asked whether this bound could be improved to $(1-\epsilon)^{\Omega(n/s)}$; this question is usually referred to as the strong parallel repetition problem. We show that the answer to this question is negative. More precisely, we consider the odd cycle game of size m, a two-prover game with value $1-1/2m$. We show that the value of the odd cycle game repeated in parallel n times is at least $1-(1/m)\cdot O(\sqrt{n})$. This implies that, for large enough n (say, $n\geq\Omega(m^2)$), the value of the odd cycle game repeated in parallel n times is at least $(1-1/4m^2)^{O(n)}$. Thus the following hold. 1. For parallel repetition of general games, the bounds of $(1-\epsilon^c)^{\Omega(n/s)}$ given in [R. Raz, SIAM J. Comput., 27 (1998), pp. 763–803; T. Holenstein, in Proceedings of STOC 2002, ACM, New York, 2002, pp. 767–775] are of the right form, up to determining the exact value of the constant $c\geq2$. 2. For parallel repetition of XOR games, unique games, and projection games, the bounds of $(1-\epsilon^2)^{\Omega(n)}$ given in [U. Feige, G. Kindler, and R. O'Donnell, in Proceedings of CCC 2007, IEEE Computer Society, Washington, DC, 2007, pp. 179–192] (for XOR games) and in [A. Rao, in Proceedings of STOC 2008, ACM, New York, 2008, pp. 1–10] (for unique and projection games) are tight. 3. For parallel repetition of the odd cycle game, the bound of $1-(1/m)\cdot\tilde{\Omega}(\sqrt{n})$ given in [U. Feige, G. Kindler, and R. O'Donnell, in Proceedings of CCC 2007, IEEE Computer Society, Washington, DC, 2007, pp. 179–192] is almost tight. A major motivation for the recent interest in the strong parallel repetition problem is that a strong parallel repetition theorem would have implied that the unique game conjecture is equivalent to the NP hardness of distinguishing between instances of Max-Cut that are at least $1-\epsilon^2$ satisfiable from instances that are at most $1-(2/\pi)\cdot\epsilon$ satisfiable. Our results suggest that this cannot be proved just by improving the known bounds on parallel repetition.

DOI
10.1109/focs.2008.49

Related papers

Rounding Parallel Repetitions of Unique Games

Boaz Barak, Moritz Hardt, Ishay Haviv +3 more

We show a connection between the semidefinite relaxation of unique games and their behavior under parallel repetition. Specifically,denoting by val(G) the value of a two-prover unique game G, andby sdpval(G) the value of a natural semidefinite program to approximate val(G), we prove that for every l epsi N, if sdpval(G) ges 1-delta, then val(Gl) ges 1-radicsldelta. Here, Gldenotes the l-fold parallel repetition of G, and s=O(log(k/delta)), where k denotes the alphabet size of the game. For the special case where G is an XOR game (i.e., k=2), we obtain the same bound but with s as an absolute constant. Our bounds on s are optimal up to a factor of O(log(1/delta)). For games with a significant gap between the quantities val(G) and sdpval(G), our result implies that val(Gl) may be much larger than val(G)l, giving a counterexample to the strong parallel repetition conjecture. In a recent breakthrough, Raz (FOCS'08) has shown such an example using the max-cut game on oddcycles. Our results are based on a generalization of his techniques.

Annual Symposium on Foundations of Computer Science•Oct 1, 2008•46 citations

No Strong Parallel Repetition with Entangled and Non-signaling Provers

Julia Kempe, Oded Regev

We consider one-round games between a classical verifier and two provers. One of the main questions in this area is the parallel repetition question: If the game is played H times in parallel, does the maximum winning probability decay exponentially in ℓ? In the classical setting, this question was answered in the affirmative by Raz. More recently the question arose whether the decay is of the form (1 - ⊖ (ε))ℓwhere 1 - ε is the value of the game and H is the number of repetitions. This question is known as the strong parallel repetition question and was motivated by its connections to the unique games conjecture. It was resolved by Raz who showed that strong parallel repetition does not hold, even in the very special case of games known as XOR games. This opens the question whether strong parallel repetition holds in the case when the provers share entanglement. Evidence for this is provided by the behavior of XOR games, which have strong (in fact perfect) parallel repetition, and by the recently proved strong parallel repetition of linear unique games. A similar question was open for games with so-called non-signaling provers. Here the best known parallel repetition theorem is due to Holenstein, and is of the form (1 - ⊖ (ε2))ℓ. We show that strong parallel repetition holds neither with entangled provers nor with non-signaling provers. In particular we obtain that Holenstein's bound is tight. Along the way we also provide a tight characterization of the asymptotic behavior of the entangled value under parallel repetition of unique games in terms of a semidefinite program.

arXiv:0911.0201•IEEE Conference on Computational Complexity (CCC)•Jun 1, 2010•33 citations

Parallel Repetition in Projection Games and a Concentration Bound

Anup Rao

A two-player game is played by cooperating players who are not allowed to communicate. A referee asks the players questions sampled from some known distribution and decides whether they win or not based on a known predicate of the questions and the players' answers. The parallel repetition of the game is the game in which the referee samples n independent pairs of questions and sends the corresponding questions to the players simultaneously. If the players cannot win the original game with probability better than $(1-\epsilon)$, what's the best they can do in the repeated game? We improve earlier results of [R. Raz, SIAM J. Comput., 27 (1998), pp. 763–803] and [T. Holenstein, Theory Comput., 5 (2009), pp. 141–172], who showed that the players cannot win all copies in the repeated game with probability better than $(1-\epsilon/2)^{\Omega(n\epsilon^2/c)}$ (here c is the length of the answers in the game), in the following ways: (i) We show that the probability of winning all copies is $(1-\epsilon/2)^{\Omega(\epsilon n)}$ as long as the game is a “projection game,” the type of game most commonly used in hardness of approximation results. (ii) We prove a concentration bound for parallel repetition (of general games) showing that for any constant $0<\delta <\epsilon$, the probability that the players win a $(1-\epsilon+\delta)$ fraction of the games in the parallel repetition is at most $\exp\left(-\Omega_{\epsilon}(\delta^3 n/c)\right)$ (here the constant may depend on $\epsilon$); our result has applications to testing Bell inequalities, since it implies that the parallel repetition of the CHSH game can be used to get an experiment that has a very large classical versus quantum gap. Our first bound is independent of the answer length and has a better dependence on $\epsilon$. By the recent work of Raz [Proceedings of the $49$th Annual IEEE Symposium on Foundations of Computer Science, 2008, pp. 369–373], this bound is tight. Our bound gives a generic way to improve the soundness of a probabilistically checkable proof (PCP), in a way that is independent of the answer length of the PCP. Using it, for every k, one can convert any q query PCP with answer length c, size $sc$, and soundness $(1-\epsilon)$ into a two-query PCP with answer length $ck$, size $O(ck (2s)^k)$, and soundness $(1-\epsilon/2q)^{\Omega(\epsilon k/q)}$. Another consequence of our bound is that the unique games conjecture of Khot [Proceedings of the $34$th Annual ACM Symposium on Theory of Computing, 2002, pp. 767–775] can now be shown to be equivalent to the following a priori weaker conjecture: There is an unbounded increasing function $f:\mathbb{R}^+\rightarrow \mathbb{R}^+$ such that for every $\epsilon> 0$, there exists an alphabet size $M(\epsilon)$ for which it is NP-hard to distinguish a unique game with alphabet size M in which a $(1-\epsilon^2)$ fraction of the constraints can be satisfied from one in which a $(1-\epsilon f(1/\epsilon))$ fraction of the constraints can be satisfied.

SIAM Journal on Computing•May 17, 2008•150 citations

A k-PROVERS PARALLEL REPETITION THEOREM FOR A VERSION OF NO-SIGNALING MODEL

Ricky Rosen

The parallel repetition theorem states that for any two provers one round game with value at most 1 - ∊ (for ∊ < 1/2), the value of the game repeated n times in parallel is at most (1 - ∊3)Ω(n/ log s) where s is the size of the answers set [9, 12]. It is not known how the value of the game decreases when there are three or more players. In this paper we address the problem of the error decrease of parallel repetition game for k-provers where k > 2. We consider a special case of the No-Signaling model and show that the error of the parallel repetition of k-provers one round game, for k > 2, in this model, decreases exponentially depending only on the error of the original game and on the number of repetitions. There were no prior results for k-provers parallel repetition for k > 2 in any model.

Discrete Mathematics Algorithms and Applications•Dec 1, 2010•0 citations

A Parallel Repetition Theorem

Ran Raz

We show that a parallel repetition of any two-prover one-round proof system (MIP(2,1)) decreases the probability of error at an exponential rate. No constructive bound was previously known. The constant in the exponent (in our analysis) depends only on the original probability of error and on the total number of possible answers of the two provers. The dependency on the total number of possible answers is logarithmic, which was recently proved to be almost the best possible [U. Feige and O. Verbitsky, Proc.11th Annual IEEE Conference on Computational Complexity, IEEE Computer Society Press, Los Alamitos, CA, 1996, pp. 70--76].

SIAM Journal on Computing•Jan 1, 1998•703 citations

Parallel Repetition of Fortified Games.

Dana Moshkovitz

The Parallel Repetition Theorem upper-bounds the value of a repeated (tensored) two prover game G⊗k in terms of the value of the game G and the number of repetitions k. Contrary to what one might have guessed, the value of G⊗k is not val(G), but rather a more complicated expression depending on properties of G. Indeed, there are numerous works aiming to understand the value of repeated games, both for general games G and for special cases. A case of particular interest is that of projection games, where the answer of the first prover determines at most one acceptable answer for the second prover. In this work we give a simple transformation, which we call “fortification”, that can be applied to any projection game. We show that for fortified games G, the value of the k-repeated game is approximately val(G). This results in nearly a quadratic improvement in the size of projection PCP with the lowest error known today. Unlike previous proofs of the parallel repetition theorem that relied on information theory or linear algebra, our proof is purely combinatorial and quite short. We then discuss the problem of derandomizing parallel repetition, and the limitations of the fortification idea in this setting. We point out a connection between the problem of derandomizing parallel repetition and the problem of composition. This connection could shed light on the so-called Projection Games Conjecture, which asks for projection PCP with minimal error. ∗dmoshkov@csail.mit.edu. Department of Electrical Engineering and Computer Science, MIT. This material is based upon work supported by the National Science Foundation under Grant Number 1218547.

Electronic colloquium on computational complexity•Jan 1, 2014•1 citation
The parallel repetition theorem states that, for any two-prover game with value 1−ϵ1-\epsilon1−ϵ (for, say, ϵ≤1/2\epsilon\leq1/2ϵ≤1/2), the value of the game repeated in parallel n times is at most (1−ϵc)Ω(n/s)(1-\epsilon^c)^{\Omega(n/s)}(1−ϵc)Ω(n/s), where s is the answer's length (of the original game) and c is a universal constant [R. Raz, SIAM J. Comput., 27 (1998), pp. 763–803]. Several researchers asked whether this bound could be improved to (1−ϵ)Ω(n/s)(1-\epsilon)^{\Omega(n/s)}(1−ϵ)Ω(n/s); this question is usually referred to as the strong parallel repetition problem. We show that the answer to this question is negative. More precisely, we consider the odd cycle game of size m, a two-prover game with value 1−1/2m1-1/2m1−1/2m. We show that the value of the odd cycle game repeated in parallel n times is at least 1−(1/m)⋅O(n)1-(1/m)\cdot O(\sqrt{n})1−(1/m)⋅O(n​). This implies that, for large enough n (say, n≥Ω(m2)n\geq\Omega(m^2)n≥Ω(m2)), the value of the odd cycle game repeated in parallel n times is at least (1−1/4m2)O(n)(1-1/4m^2)^{O(n)}(1−1/4m2)O(n). Thus the following hold. 1. For parallel repetition of general games, the bounds of (1−ϵc)Ω(n/s)(1-\epsilon^c)^{\Omega(n/s)}(1−ϵc)Ω(n/s) given in [R. Raz, SIAM J. Comput., 27 (1998), pp. 763–803; T. Holenstein, in Proceedings of STOC 2002, ACM, New York, 2002, pp. 767–775] are of the right form, up to determining the exact value of the constant c≥2c\geq2c≥2. 2. For parallel repetition of XOR games, unique games, and projection games, the bounds of (1−ϵ2)Ω(n)(1-\epsilon^2)^{\Omega(n)}(1−ϵ2)Ω(n) given in [U. Feige, G. Kindler, and R. O'Donnell, in Proceedings of CCC 2007, IEEE Computer Society, Washington, DC, 2007, pp. 179–192] (for XOR games) and in [A. Rao, in Proceedings of STOC 2008, ACM, New York, 2008, pp. 1–10] (for unique and projection games) are tight. 3. For parallel repetition of the odd cycle game, the bound of 1−(1/m)⋅Ω~(n)1-(1/m)\cdot\tilde{\Omega}(\sqrt{n})1−(1/m)⋅Ω~(n​) given in [U. Feige, G. Kindler, and R. O'Donnell, in Proceedings of CCC 2007, IEEE Computer Society, Washington, DC, 2007, pp. 179–192] is almost tight. A major motivation for the recent interest in the strong parallel repetition problem is that a strong parallel repetition theorem would have implied that the unique game conjecture is equivalent to the NP hardness of distinguishing between instances of Max-Cut that are at least 1−ϵ21-\epsilon^21−ϵ2 satisfiable from instances that are at most 1−(2/π)⋅ϵ1-(2/\pi)\cdot\epsilon1−(2/π)⋅ϵ satisfiable. Our results suggest that this cannot be proved just by improving the known bounds on parallel repetition.
We show a connection between the semidefinite relaxation of unique games and their behavior under parallel repetition. Specifically,denoting by val(G) the value of a two-prover unique game G, andby sdpval(G) the value of a natural semidefinite program to approximate val(G), we prove that for every l epsi N, if sdpval(G) ges 1-delta, then val(Gl) ges 1-radicsldelta. Here, Gldenotes the l-fold parallel repetition of G, and s=O(log(k/delta)), where k denotes the alphabet size of the game. For the special case where G is an XOR game (i.e., k=2), we obtain the same bound but with s as an absolute constant. Our bounds on s are optimal up to a factor of O(log(1/delta)). For games with a significant gap between the quantities val(G) and sdpval(G), our result implies that val(Gl) may be much larger than val(G)l, giving a counterexample to the strong parallel repetition conjecture. In a recent breakthrough, Raz (FOCS'08) has shown such an example using the max-cut game on oddcycles. Our results are based on a generalization of his techniques.
We consider one-round games between a classical verifier and two provers. One of the main questions in this area is the parallel repetition question: If the game is played H times in parallel, does the maximum winning probability decay exponentially in ℓ? In the classical setting, this question was answered in the affirmative by Raz. More recently the question arose whether the decay is of the form (1 - ⊖ (ε))ℓwhere 1 - ε is the value of the game and H is the number of repetitions. This question is known as the strong parallel repetition question and was motivated by its connections to the unique games conjecture. It was resolved by Raz who showed that strong parallel repetition does not hold, even in the very special case of games known as XOR games. This opens the question whether strong parallel repetition holds in the case when the provers share entanglement. Evidence for this is provided by the behavior of XOR games, which have strong (in fact perfect) parallel repetition, and by the recently proved strong parallel repetition of linear unique games. A similar question was open for games with so-called non-signaling provers. Here the best known parallel repetition theorem is due to Holenstein, and is of the form (1 - ⊖ (ε2))ℓ. We show that strong parallel repetition holds neither with entangled provers nor with non-signaling provers. In particular we obtain that Holenstein's bound is tight. Along the way we also provide a tight characterization of the asymptotic behavior of the entangled value under parallel repetition of unique games in terms of a semidefinite program.
A two-player game is played by cooperating players who are not allowed to communicate. A referee asks the players questions sampled from some known distribution and decides whether they win or not based on a known predicate of the questions and the players' answers. The parallel repetition of the game is the game in which the referee samples n independent pairs of questions and sends the corresponding questions to the players simultaneously. If the players cannot win the original game with probability better than (1−ϵ)(1-\epsilon)(1−ϵ), what's the best they can do in the repeated game? We improve earlier results of [R. Raz, SIAM J. Comput., 27 (1998), pp. 763–803] and [T. Holenstein, Theory Comput., 5 (2009), pp. 141–172], who showed that the players cannot win all copies in the repeated game with probability better than (1−ϵ/2)Ω(nϵ2/c)(1-\epsilon/2)^{\Omega(n\epsilon^2/c)}(1−ϵ/2)Ω(nϵ2/c) (here c is the length of the answers in the game), in the following ways: (i) We show that the probability of winning all copies is (1−ϵ/2)Ω(ϵn)(1-\epsilon/2)^{\Omega(\epsilon n)}(1−ϵ/2)Ω(ϵn) as long as the game is a “projection game,” the type of game most commonly used in hardness of approximation results. (ii) We prove a concentration bound for parallel repetition (of general games) showing that for any constant 0<δ<ϵ0<\delta <\epsilon0<δ<ϵ, the probability that the players win a (1−ϵ+δ)(1-\epsilon+\delta)(1−ϵ+δ) fraction of the games in the parallel repetition is at most exp⁡(−Ωϵ(δ3n/c))\exp\left(-\Omega_{\epsilon}(\delta^3 n/c)\right)exp(−Ωϵ​(δ3n/c)) (here the constant may depend on ϵ\epsilonϵ); our result has applications to testing Bell inequalities, since it implies that the parallel repetition of the CHSH game can be used to get an experiment that has a very large classical versus quantum gap. Our first bound is independent of the answer length and has a better dependence on ϵ\epsilonϵ. By the recent work of Raz [Proceedings of the 494949th Annual IEEE Symposium on Foundations of Computer Science, 2008, pp. 369–373], this bound is tight. Our bound gives a generic way to improve the soundness of a probabilistically checkable proof (PCP), in a way that is independent of the answer length of the PCP. Using it, for every k, one can convert any q query PCP with answer length c, size scscsc, and soundness (1−ϵ)(1-\epsilon)(1−ϵ) into a two-query PCP with answer length ckckck, size O(ck(2s)k)O(ck (2s)^k)O(ck(2s)k), and soundness (1−ϵ/2q)Ω(ϵk/q)(1-\epsilon/2q)^{\Omega(\epsilon k/q)}(1−ϵ/2q)Ω(ϵk/q). Another consequence of our bound is that the unique games conjecture of Khot [Proceedings of the 343434th Annual ACM Symposium on Theory of Computing, 2002, pp. 767–775] can now be shown to be equivalent to the following a priori weaker conjecture: There is an unbounded increasing function f:R+→R+f:\mathbb{R}^+\rightarrow \mathbb{R}^+f:R+→R+ such that for every ϵ>0\epsilon> 0ϵ>0, there exists an alphabet size M(ϵ)M(\epsilon)M(ϵ) for which it is NP-hard to distinguish a unique game with alphabet size M in which a (1−ϵ2)(1-\epsilon^2)(1−ϵ2) fraction of the constraints can be satisfied from one in which a (1−ϵf(1/ϵ))(1-\epsilon f(1/\epsilon))(1−ϵf(1/ϵ)) fraction of the constraints can be satisfied.
The parallel repetition theorem states that for any two provers one round game with value at most 1 - ∊ (for ∊ < 1/2), the value of the game repeated n times in parallel is at most (1 - ∊3)Ω(n/ log s) where s is the size of the answers set [9, 12]. It is not known how the value of the game decreases when there are three or more players. In this paper we address the problem of the error decrease of parallel repetition game for k-provers where k > 2. We consider a special case of the No-Signaling model and show that the error of the parallel repetition of k-provers one round game, for k > 2, in this model, decreases exponentially depending only on the error of the original game and on the number of repetitions. There were no prior results for k-provers parallel repetition for k > 2 in any model.
We show that a parallel repetition of any two-prover one-round proof system (MIP(2,1)) decreases the probability of error at an exponential rate. No constructive bound was previously known. The constant in the exponent (in our analysis) depends only on the original probability of error and on the total number of possible answers of the two provers. The dependency on the total number of possible answers is logarithmic, which was recently proved to be almost the best possible [U. Feige and O. Verbitsky, Proc.11th Annual IEEE Conference on Computational Complexity, IEEE Computer Society Press, Los Alamitos, CA, 1996, pp. 70--76].
The Parallel Repetition Theorem upper-bounds the value of a repeated (tensored) two prover game G⊗k in terms of the value of the game G and the number of repetitions k. Contrary to what one might have guessed, the value of G⊗k is not val(G), but rather a more complicated expression depending on properties of G. Indeed, there are numerous works aiming to understand the value of repeated games, both for general games G and for special cases. A case of particular interest is that of projection games, where the answer of the first prover determines at most one acceptable answer for the second prover. In this work we give a simple transformation, which we call “fortification”, that can be applied to any projection game. We show that for fortified games G, the value of the k-repeated game is approximately val(G). This results in nearly a quadratic improvement in the size of projection PCP with the lowest error known today. Unlike previous proofs of the parallel repetition theorem that relied on information theory or linear algebra, our proof is purely combinatorial and quite short. We then discuss the problem of derandomizing parallel repetition, and the limitations of the fortification idea in this setting. We point out a connection between the problem of derandomizing parallel repetition and the problem of composition. This connection could shed light on the so-called Projection Games Conjecture, which asks for projection PCP with minimal error. ∗dmoshkov@csail.mit.edu. Department of Electrical Engineering and Computer Science, MIT. This material is based upon work supported by the National Science Foundation under Grant Number 1218547.