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:2611.01339

The Exact Communication Threshold for Parallel Repetition

Daiki Suruga

Published Oct 31, 2026• 0 citations
arXivHTMLPDF

Abstract

The parallel repetition theorem is a fundamental tool in theoretical computer science, showing that the probability of winning all $n$ independent instances of a finite two-player game decays exponentially in $n$, provided that the game has no perfect strategy. The classical theorem assumes that the players cannot communicate, raising the question of how much communication can be allowed while preserving this exponential decay. For every finite total relation $g$ and arbitrary input distribution $μ$, we prove exponential decay at every fixed communication rate below a quantity called zero-error internal information complexity, denoted by $\mathrm{IC}_μ(g,0)$. Together with known results showing that $n\,\mathrm{IC}_μ(g,0)+o(n)$ bits of communication suffice to solve all $n$ instances with success probability tending to one, our bound determines the exact communication threshold. As a by-product, we obtain exact characterizations of amortized distributional and randomized communication complexity under the global-error criterion.

DOI
10.48550/arxiv.2611.01339

Related papers

Non-Signaling 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 Gn(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 paper, the case of multiplayer non-signaling 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-signaling players win more than a fraction 1-α+β of the n games is exponentially small in nβ2for every 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.

arXiv:1411.1582•IEEE Transactions on Information Theory•Jan 8, 2016•26 citations

Concentration Bounds from Parallel Repetition Theorems

Taylor Hornby

This thesis contributes to the study of parallel repetition theorems and concentration bounds for nonlocal games and quantum interactive proofs. We make the following contributions: \n \n- A lemma that is useful for converting parallel repetition theorems (bounds on the probability of winning all instances of a nonlocal game which is being repeated in parallel) into concentration bounds (bounds on winning a certain fraction of the instances). \n \n- Exponentially-decaying concentration bounds for two-player games on the uniform distribution and k-player free games, against quantum strategies. \n \n- A proof that given a quantum interactive proof system with parameters α (the probability with which the verifier can be convinced to accept when they should accept) and β (the soundness error), as long as α > β, both the soundness error and completeness error can be reduced exponentially by repeating the protocol in parallel and requiring an (α + β)/2 fraction of the repetitions to be won. Our result requires a log-factor more repetitions than are necessary in the classical case.

•Aug 22, 2018•1 citation

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•11 citations

Multiplayer Parallel Repetition for Expanding 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>=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•Leibniz international proceedings in informatics•Oct 26, 2016•18 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•159 citations

Threshold parallel repetition for finite-dimensional entangled games

OpenAI

For every finite two-player game with entangled value v<1, we prove exponential decay for the probability of winning at least a v+\delta fraction of k independent repetitions, uniformly over all finite-dimensional joint strategies. The result allows arbitrary correlated question distributions and holds for every 0\lt \delta\lt 1-v and k\ge1. Its universal rate is proportional to \delta^5/(1+\log(|\mathcal A||\mathcal B|)), where \mathcal A,\mathcal B are the answer alphabets. For each fixed question distribution, we also obtain an explicit cubic rate in \delta.

•Oct 6, 2026•0 citations
The parallel repetition theorem is a fundamental tool in theoretical computer science, showing that the probability of winning all nnn independent instances of a finite two-player game decays exponentially in nnn, provided that the game has no perfect strategy. The classical theorem assumes that the players cannot communicate, raising the question of how much communication can be allowed while preserving this exponential decay. For every finite total relation ggg and arbitrary input distribution μμμ, we prove exponential decay at every fixed communication rate below a quantity called zero-error internal information complexity, denoted by ICμ(g,0)\mathrm{IC}_μ(g,0)ICμ​(g,0). Together with known results showing that n ICμ(g,0)+o(n)n\,\mathrm{IC}_μ(g,0)+o(n)nICμ​(g,0)+o(n) bits of communication suffice to solve all nnn instances with success probability tending to one, our bound determines the exact communication threshold. As a by-product, we obtain exact characterizations of amortized distributional and randomized communication complexity under the global-error criterion.
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 Gn(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 paper, the case of multiplayer non-signaling 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-signaling players win more than a fraction 1-α+β of the n games is exponentially small in nβ2for every 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.
This thesis contributes to the study of parallel repetition theorems and concentration bounds for nonlocal games and quantum interactive proofs. We make the following contributions: \n \n- A lemma that is useful for converting parallel repetition theorems (bounds on the probability of winning all instances of a nonlocal game which is being repeated in parallel) into concentration bounds (bounds on winning a certain fraction of the instances). \n \n- Exponentially-decaying concentration bounds for two-player games on the uniform distribution and k-player free games, against quantum strategies. \n \n- A proof that given a quantum interactive proof system with parameters α (the probability with which the verifier can be convinced to accept when they should accept) and β (the soundness error), as long as α > β, both the soundness error and completeness error can be reduced exponentially by repeating the protocol in parallel and requiring an (α + β)/2 fraction of the repetitions to be won. Our result requires a log-factor more repetitions than are necessary in the classical case.
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).
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.
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.
For every finite two-player game with entangled value v<1, we prove exponential decay for the probability of winning at least a v+\delta fraction of k independent repetitions, uniformly over all finite-dimensional joint strategies. The result allows arbitrary correlated question distributions and holds for every 0\lt \delta\lt 1-v and k\ge1. Its universal rate is proportional to \delta^5/(1+\log(|\mathcal A||\mathcal B|)), where \mathcal A,\mathcal B are the answer alphabets. For each fixed question distribution, we also obtain an explicit cubic rate in \delta.