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

Discrete Mathematics Algorithms and Applications

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

Ricky Rosen

Published Dec 1, 2010• 1 citation
Publisher

Abstract

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.

DOI
10.1142/s1793830910000802

Related papers

On the Parallel Repetition of Multi-Player Games: The No-Signaling Case

Harry Buhrman, Serge Fehr, Christian Schaffner

We consider the natural extension of two-player nonlocal games to an arbitrary number of players. An important question for such nonlocal games is their behavior under parallel repetition. For two-player nonlocal games, it is known that both the classical and the non-signaling value of any game converges to zero exponentially fast under parallel repetition, given that the game is non-trivial to start with (i.e., has classical/non-signaling value <1). Very recent results show similar behavior for the quantum value of a two-player game under parallel repetition. For nonlocal games with three or more players, very little is known up to present on their behavior under parallel repetition; this is true for the classical, the quantum and the non-signaling value. In this work, we show a parallel repetition theorem for the non-signaling value of a large class of multi-player games, for an arbitrary number of players. Our result applies to all multi-player games for which all possible combinations of questions have positive probability; this class in particular includes all free games, in which the questions to the players are chosen independently. Specifically, we prove that if the original game has a non-signaling value smaller than 1, then the non-signaling value of the $n$-fold parallel repetition is exponentially small in $n$. Our parallel repetition theorem for multi-player games is weaker than the known parallel repetition results for two-player games in that the rate at which the non-signaling value of the game decreases not only depends on the non-signaling value of the original game (and the number of possible responses), but on the complete description of the game. Nevertheless, we feel that our result is a first step towards a better understanding of the parallel repetition of nonlocal games with more than two players.

arXiv:1312.7455•Leibniz international proceedings in informatics•Dec 28, 2013•15 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•32 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•724 citations

REMARKS ON A QUERY-BASED VARIANT OF THE PARALLEL REPETITION THEOREM

Oleg Verbitsky

The Parallel Repetition Theorem says that n-fold parallel execution of a two-prover one-round interactive proof system reduces the error probability exponentially in n. The bound on the error probability of the parallelized system depends on the error probability and the answer size of the single proof system. It is still unknown whether the theorem holds true with a bound depending only on the query size. This kind of a bound may be preferable whenever the query size is considerably smaller than the answer size, what really happens in some cryptographic protocols. Such a bound is only known in the case that queries to the provers are independent. The present paper extends this result to some cases of strong correlation between queries. In particular, a query-based variant of the Parallel Repetition Theorem is proven when the graph of dependence between queries to the provers is a tree and, in a bit weaker form, when this graph is a cycle.

International Journal of Foundations of Computer Science•Aug 1, 2001•0 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

A Counterexample to Strong Parallel Repetition

Ran Raz

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.

SIAM Journal on Computing•Oct 1, 2008•84 citations
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 consider the natural extension of two-player nonlocal games to an arbitrary number of players. An important question for such nonlocal games is their behavior under parallel repetition. For two-player nonlocal games, it is known that both the classical and the non-signaling value of any game converges to zero exponentially fast under parallel repetition, given that the game is non-trivial to start with (i.e., has classical/non-signaling value <1). Very recent results show similar behavior for the quantum value of a two-player game under parallel repetition. For nonlocal games with three or more players, very little is known up to present on their behavior under parallel repetition; this is true for the classical, the quantum and the non-signaling value. In this work, we show a parallel repetition theorem for the non-signaling value of a large class of multi-player games, for an arbitrary number of players. Our result applies to all multi-player games for which all possible combinations of questions have positive probability; this class in particular includes all free games, in which the questions to the players are chosen independently. Specifically, we prove that if the original game has a non-signaling value smaller than 1, then the non-signaling value of the nnn-fold parallel repetition is exponentially small in nnn. Our parallel repetition theorem for multi-player games is weaker than the known parallel repetition results for two-player games in that the rate at which the non-signaling value of the game decreases not only depends on the non-signaling value of the original game (and the number of possible responses), but on the complete description of the game. Nevertheless, we feel that our result is a first step towards a better understanding of the parallel repetition of nonlocal games with more than two players.
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.
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 says that n-fold parallel execution of a two-prover one-round interactive proof system reduces the error probability exponentially in n. The bound on the error probability of the parallelized system depends on the error probability and the answer size of the single proof system. It is still unknown whether the theorem holds true with a bound depending only on the query size. This kind of a bound may be preferable whenever the query size is considerably smaller than the answer size, what really happens in some cryptographic protocols. Such a bound is only known in the case that queries to the provers are independent. The present paper extends this result to some cases of strong correlation between queries. In particular, a query-based variant of the Parallel Repetition Theorem is proven when the graph of dependence between queries to the provers is a tree and, in a bit weaker form, when this graph is a cycle.
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.
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.