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:cs/0607139 · Theory of Computing

Parallel repetition: simplifications and the no-signaling case

Thomas Holenstein

Published Jan 1, 2009• 123 citations
arXivHTMLPDF

Abstract

$ \newcommand{\vbar}{\bar{v}} $ Consider a game where a referee chooses $(x,y)$ according to a publicly known distribution, sends $x$ to Alice, and $y$ to Bob. Without communicating with each other, Alice responds with a value $a$ and Bob responds with a value $b$. Alice and Bob jointly win if a publicly known predicate $Q(x,y,a,b)$ is satisfied. Assume that the maximum probability that Alice and Bob can win in such a game is $v<1$. Raz (SIAM J. Comput. 27, 1998) shows that if the game is repeated $n$ times in parallel, then the probability that Alice and Bob win all games simultaneously is at most $\vbar^{\tfrac{n}{\log(s)}}$, where $s$ is the maximal number of possible responses from Alice and Bob in the initial game, and $\vbar<1$ is a constant depending only on $v$. In this work, we simplify Raz's proof in various ways and thus shorten it significantly. Further we study the case where Alice and Bob are not restricted to local computations and can use any strategy which does not imply communication between them.

DOI
10.4086/toc.2009.v005a008

Related papers

Parallel repetition

Thomas Holenstein

Consider a game where a refereed chooses (x,y) according to a publiclyknown distribution PXY, sends x to Alice, and y to Bob. Withoutcommunicating with each other, Alice responds with a value "a" and Bobresponds with a value "b". Alice and Bob jointly win if a publiclyknown predicate Q(x,y,a,b) holds. Let such a game be given and assume that the maximum probabilitythat Alice and Bob can win is v<1. Raz (SIAM J. Comput. 27, 1998)shows that if the game is repeated n times in parallel, then the probability that Alice and Bob win all games simultaneously is at most v'(n/log(s)), where s is the maximal number of possible responses from Alice and Bob in the initial game, and v' is a constant depending only on v. In this work, we simplify Raz's proof in various ways and thus shorten it significantly. Further we study the case where Alice and Bob are not restricted to local computations and can use any strategy which does not imply communication among them.

ACM Symposium on Theory of Computing (STOC)•Jun 11, 2007•138 citations

Parallel Repetition of Free Entangled Games: Simplification and Improvements

André Chailloux, Scarpa, Giannicola

In a two-player game, two cooperating but non communicating players, Alice and Bob, receive inputs taken from a probability distribution. Each of them produces an output and they win the game if they satisfy some predicate on their inputs/outputs. The entangled value $ω^*(G)$ of a game $G$ is the maximum probability that Alice and Bob can win the game if they are allowed to share an entangled state prior to receiving their inputs. The $n$-fold parallel repetition $G^n$ of $G$ consists of $n$ instances of $G$ where Alice and Bob receive all the inputs at the same time and must produce all the outputs at the same time. They win $G^n$ if they win each instance of $G$. Recently, there has been a series of works showing parallel repetition with exponential decay for projection games [DSV13], games on the uniform distribution [CS14] and for free games, i.e. games on a product distribution [JPY13]. This article is meant to be a follow up of [CS14], where we improve and simplify several parts of our previous paper. Our main result is that for any free game $G$ with value $ω^*(G)=1-\varepsilon$, we have $ω^*(G^n) \le (1 - \varepsilon^2)^{Ω(\frac{n}{\log(l)})}$ where $l$ is the size of the output set of the game. This result improves on both the results in [JPY13] and [CS14]. The framework we use can also be extended to free projection games. We show that for a free projection game $G$ with value $ω^*(G)=1-\varepsilon$, we have $ω^*(G^n) \le (1 - \varepsilon)^{Ω(n)}$.

arXiv:1410.4397•Oct 16, 2014•7 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

Parallel Repetition of Entangled Games

Julia Kempe, Thomas Vidick

We consider one-round games between a classical referee and two players. One of the main questions in this area is the parallel repetition question: Is there a way to decrease the maximum winning probability of a game without increasing the number of rounds or the number of players? Classically, efforts to resolve this question, open for many years, have culminated in Raz's celebrated parallel repetition theorem on one hand, and in efficient product testers for PCPs on the other. In the case where players share entanglement, the only previously known results are for special cases of games, and are based on techniques that seem inherently limited. Here we show for the first time that the maximum success probability of entangled games can be reduced through parallel repetition, provided it was not initially 1. Our proof is inspired by a seminal result of Feige and Kilian in the context of classical two-prover one-round interactive proofs. One of the main components in our proof is an orthogonalization lemma for operators, which might be of independent interest.

arXiv:1012.4728•Dec 21, 2010•2 citations

Non-signalling parallel repetition using de Finetti reductions

Rotem Arnon-Friedman, Renato Renner, Thomas Vidick

In the context of multiplayer games, the parallel repetition problem can be phrased as follows: given a game $G$ with optimal winning probability $1-α$ and its repeated version $G^n$ (in which $n$ games are played together, in parallel), can the players use strategies that are substantially better than ones in which each game is played independently? This question is relevant in physics for the study of correlations and plays an important role in computer science in the context of complexity and cryptography. In this work the case of multiplayer non-signalling games is considered, i.e., the only restriction on the players is that they are not allowed to communicate during the game. For complete-support games (games where all possible combinations of questions have non-zero probability to be asked) with any number of players we prove a threshold theorem stating that the probability that non-signalling players win more than a fraction $1-α+β$ of the $n$ games is exponentially small in $nβ^2$, for every $0\leq β\leq α$. For games with incomplete support we derive a similar statement, for a slightly modified form of repetition. The result is proved using a new technique, based on a recent de Finetti theorem, which allows us to avoid central technical difficulties that arise in standard proofs of parallel repetition theorems.

arXiv:1411.1582•Nov 6, 2014•6 citations

Parallel repetition of entangled games

Julia Kempe, Thomas Vidick

We consider one-round games between a classical referee and two players. One of the main questions in this area is the parallel repetition question: Is there a way to decrease the maximum winning probability of a game without increasing the number of rounds or the number of players? Classically, efforts to resolve this question, open for many years, have culminated in Raz's celebrated parallel repetition theorem on one hand, and in efficient product testers for PCPs on the other.

ACM Symposium on Theory of Computing (STOC)•Jun 6, 2011•44 citations
\newcommand{\vbar}{\bar{v}} Consider a game where a referee chooses (x,y)(x,y)(x,y) according to a publicly known distribution, sends xxx to Alice, and yyy to Bob. Without communicating with each other, Alice responds with a value aaa and Bob responds with a value bbb. Alice and Bob jointly win if a publicly known predicate Q(x,y,a,b)Q(x,y,a,b)Q(x,y,a,b) is satisfied. Assume that the maximum probability that Alice and Bob can win in such a game is v<1v<1v<1. Raz (SIAM J. Comput. 27, 1998) shows that if the game is repeated nnn times in parallel, then the probability that Alice and Bob win all games simultaneously is at most \vbarnlog⁡(s)\vbar^{\tfrac{n}{\log(s)}}\vbarlog(s)n​, where sss is the maximal number of possible responses from Alice and Bob in the initial game, and \vbar<1\vbar<1\vbar<1 is a constant depending only on vvv. In this work, we simplify Raz's proof in various ways and thus shorten it significantly. Further we study the case where Alice and Bob are not restricted to local computations and can use any strategy which does not imply communication between them.
Consider a game where a refereed chooses (x,y) according to a publiclyknown distribution PXY, sends x to Alice, and y to Bob. Withoutcommunicating with each other, Alice responds with a value "a" and Bobresponds with a value "b". Alice and Bob jointly win if a publiclyknown predicate Q(x,y,a,b) holds. Let such a game be given and assume that the maximum probabilitythat Alice and Bob can win is v<1. Raz (SIAM J. Comput. 27, 1998)shows that if the game is repeated n times in parallel, then the probability that Alice and Bob win all games simultaneously is at most v'(n/log(s)), where s is the maximal number of possible responses from Alice and Bob in the initial game, and v' is a constant depending only on v. In this work, we simplify Raz's proof in various ways and thus shorten it significantly. Further we study the case where Alice and Bob are not restricted to local computations and can use any strategy which does not imply communication among them.
In a two-player game, two cooperating but non communicating players, Alice and Bob, receive inputs taken from a probability distribution. Each of them produces an output and they win the game if they satisfy some predicate on their inputs/outputs. The entangled value ω∗(G)ω^*(G)ω∗(G) of a game GGG is the maximum probability that Alice and Bob can win the game if they are allowed to share an entangled state prior to receiving their inputs. The nnn-fold parallel repetition GnG^nGn of GGG consists of nnn instances of GGG where Alice and Bob receive all the inputs at the same time and must produce all the outputs at the same time. They win GnG^nGn if they win each instance of GGG. Recently, there has been a series of works showing parallel repetition with exponential decay for projection games [DSV13], games on the uniform distribution [CS14] and for free games, i.e. games on a product distribution [JPY13]. This article is meant to be a follow up of [CS14], where we improve and simplify several parts of our previous paper. Our main result is that for any free game GGG with value ω∗(G)=1−εω^*(G)=1-\varepsilonω∗(G)=1−ε, we have ω∗(Gn)≤(1−ε2)Ω(nlog⁡(l))ω^*(G^n) \le (1 - \varepsilon^2)^{Ω(\frac{n}{\log(l)})}ω∗(Gn)≤(1−ε2)Ω(log(l)n​) where lll is the size of the output set of the game. This result improves on both the results in [JPY13] and [CS14]. The framework we use can also be extended to free projection games. We show that for a free projection game GGG with value ω∗(G)=1−εω^*(G)=1-\varepsilonω∗(G)=1−ε, we have ω∗(Gn)≤(1−ε)Ω(n)ω^*(G^n) \le (1 - \varepsilon)^{Ω(n)}ω∗(Gn)≤(1−ε)Ω(n).
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.
We consider one-round games between a classical referee and two players. One of the main questions in this area is the parallel repetition question: Is there a way to decrease the maximum winning probability of a game without increasing the number of rounds or the number of players? Classically, efforts to resolve this question, open for many years, have culminated in Raz's celebrated parallel repetition theorem on one hand, and in efficient product testers for PCPs on the other. In the case where players share entanglement, the only previously known results are for special cases of games, and are based on techniques that seem inherently limited. Here we show for the first time that the maximum success probability of entangled games can be reduced through parallel repetition, provided it was not initially 1. Our proof is inspired by a seminal result of Feige and Kilian in the context of classical two-prover one-round interactive proofs. One of the main components in our proof is an orthogonalization lemma for operators, which might be of independent interest.
In the context of multiplayer games, the parallel repetition problem can be phrased as follows: given a game GGG with optimal winning probability 1−α1-α1−α and its repeated version GnG^nGn (in which nnn games are played together, in parallel), can the players use strategies that are substantially better than ones in which each game is played independently? This question is relevant in physics for the study of correlations and plays an important role in computer science in the context of complexity and cryptography. In this work the case of multiplayer non-signalling games is considered, i.e., the only restriction on the players is that they are not allowed to communicate during the game. For complete-support games (games where all possible combinations of questions have non-zero probability to be asked) with any number of players we prove a threshold theorem stating that the probability that non-signalling players win more than a fraction 1−α+β1-α+β1−α+β of the nnn games is exponentially small in nβ2nβ^2nβ2, for every 0≤β≤α0\leq β\leq α0≤β≤α. For games with incomplete support we derive a similar statement, for a slightly modified form of repetition. The result is proved using a new technique, based on a recent de Finetti theorem, which allows us to avoid central technical difficulties that arise in standard proofs of parallel repetition theorems.