betaFeedback

WorksComputer Science

The Exact Communication Threshold for Parallel Repetition

Abstract

The parallel repetition theorem is a fundamental tool in theoretical computer science, showing that the probability of winning all nn independent instances of a finite two-player game decays exponentially in nn, 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 gg 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). Together with known results showing that n ICμ(g,0)+o(n)n\,\mathrm{IC}_μ(g,0)+o(n) bits of communication suffice to solve all nn 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.

AI disclosure

The author used ChatGPT (OpenAI) to discover the main result and assist with literature searches and the preparation and revision of this manuscript. Access was provided through OpenAI’s ChatGPT for Academic Researchers program. For transparency, an earlier draft of this manuscript, written by ChatGPT, is available on the Open Science Framework (OSF). The author reviewed and improved the material incorporated into the manuscript and takes full responsibility for its content.

Introduction

For a finite two-player game with a total relation gg and question distribution μ\mu, let ω(g,μ)\omega(g,\mu) denote its largest winning probability without communication. The classical parallel repetition theorem of Refs. [24, 16] states that, if ω(g,μ)<1\omega(g,\mu)<1, the largest probability of winning all nn independent instances (gn,μ⊗n)(g^n,\mu^{\otimes n}) satisfies

ω(gn,μ⊗n)≤2−αn\omega(g^n,\mu^{\otimes n}) \le2^{-\alpha n}

for some constant α=α(g,μ)>0\alpha=\alpha(g,\mu)>0. Parallel repetition theorems have diverse applications: they are used to reduce soundness error in two-prover interactive proofs [24] and play a central role in hardness-of-approximation results for constraint satisfaction, Clique, and Set Cover [Hås01, Fei98, DS14] for example.

This paper studies how this exponential decay changes when Alice and Bob are allowed to communicate after receiving their question strings. Allowing enough communication eliminates the decay altogether: exchanging the full inputs guarantees success because gg is total.

The classical theorems already give a partial answer: exponential decay persists when the communication is sufficiently small. Indeed, for a protocol Πn\Pi_n for gng^n communicating at most cnc_n bits, guessing its transcript using shared randomness gives a zero-communication strategy whose success probability is at least 2−cn⋅Pr⁡[Πn succeeds]2^{-c_n}\cdot\Pr[\Pi_n\text{ succeeds}]; see, e.g., the transcript guessing argument [19 Section 4.1]. The repeated-game value and the preceding classical bound therefore give

Pr⁡μ⊗n[Πn succeeds]≤2cnω(gn,μ⊗n)≤2−(nα−cn).\Pr_{\mu^{\otimes n}}[\Pi_n\text{ succeeds}] \le2^{c_n}\omega(g^n,\mu^{\otimes n}) \le2^{-(n\alpha-c_n)}.

Hence, the success probability of the protocol Πn\Pi_n decays exponentially whenever cn≪αnc_n\ll\alpha n. However, α\alpha can be very small; α<1\alpha<1 whenever ω(g,μ)>1/2\omega(g,\mu)>1/2,1 and even the exponent supplied by the current best bound Ref. [16] is also less than one. When α<1\alpha<1, the condition cn≪αnc_n\ll\alpha n requires cn/n≪1c_n/n\ll1, and therefore, the communication allowance obtained by this argument is below one bit per instance. This restriction to less than one bit can be far from optimal: for some functions gg on mm-bit inputs and suitable input distributions, the success probability is known to decay exponentially in nn even with Ω(nm)\Omega(nm) bits of communication; see Ref. [23 Corollary 23].

To fill this gap, this paper investigates the exact communication threshold:

how much communication can be allowed while every protocol still has exponentially small success probability, and how much suffices for success tending to one?

This extends the question addressed by classical parallel repetition, which is recovered when cn=0c_n=0.

This paper determines this exact threshold on the asymptotic rate lim⁡ncn/n\lim_n c_n/n for every finite total relation gg and arbitrary input distribution μ\mu: it equals IC⁡μ(g,0)\operatorname{IC}_{\mu}(g,0), the zero-error value of a quantity called information complexity (see Ref. [4]). Formally, for every δ>0\delta>0, we prove that every two-party protocol Πn\Pi_n having the worst-case cost ∣Πn∣|\Pi_n| at most n(IC⁡μ(g,0)−δ)n(\operatorname{IC}_{\mu}(g,0)-\delta) succeeds on (gn,μ⊗n)(g^n,\mu^{\otimes n}) with probability at most 2−Ω(n)2^{-\Omega(n)}. Conversely, the compression result of Ref. [4] gives protocols Πn\Pi_n with communication cost n(IC⁡μ(g,0)+o(1))n(\operatorname{IC}_{\mu}(g,0)+o(1)) that succeed with probability tending to one. Together, these bounds also determine the exact asymptotic distributional communication complexity of gng^n for every global error ϵ∈(0,1)\epsilon\in(0,1); we additionally obtain the corresponding characterization for randomized communication complexity. Our result therefore refines classical parallel repetition by identifying the exact communication threshold below which exponential decay persists. Section 1.1 gives the precise statements and consequences.

Our results and consequences

To state our main result precisely, we first introduce the setting and notation. Let g⊆X×Y×A×Bg\subseteq\mathcal{X}\times\mathcal{Y}\times\mathcal{A}\times\mathcal{B} be a relation on finite sets, where X×Y\mathcal{X}\times\mathcal{Y} is the set of inputs, and A×B\mathcal{A}\times\mathcal{B} is the set of outputs. (We assume that gg is total, meaning that a valid output pair exists for every input pair.) Let μ\mu be an arbitrary distribution on X×Y\mathcal{X}\times\mathcal{Y}, and write μ⊗n\mu^{\otimes n} for its nn-i.i.d. distribution. We consider general two-party protocols with an arbitrary number of rounds and measure their worst-case communication cost, formally given in Section 2.

Let us also briefly introduce a quantity that plays a crucial role in our result. This quantity, called internal information complexity, is an information-theoretic measure used in communication complexity; see Refs. [4, 5, 25]. Specifically, our main result uses the zero-error internal information complexity of gg under the input distribution μ\mu, denoted by IC⁡μ(g,0)\operatorname{IC}_{\mu}(g,0). The formal definitions are given in Section 2.

Our main result is the following, which is a simplified version of Theorem 3.1; the full statement also gives explicit bounds on the exponent κ\kappa.

Theorem 1.1 (Main result). For every 0≤R<IC⁡μ(g,0)0\le R<\operatorname{IC}_{\mu}(g,0), there exists κ=κ(g,μ,R)>0\kappa=\kappa(g,\mu,R)>0 such that, for every n≥1n\ge1, every protocol Πn\Pi_n for gng^n communicating at most nRnR bits satisfies

Pr⁡μ⊗n[Πn succeeds on every coordinate]≤2−κn.\Pr_{\mu^{\otimes n}}[\Pi_n\text{ succeeds on every coordinate}] \le2^{-\kappa n}.

Thus, every communication rate below IC⁡μ(g,0)\operatorname{IC}_{\mu}(g,0) forces exponentially small success probability, with an exponent independent of the protocol and the number of instances. Consequently, even protocols with success probability 2−o(n)2^{-o(n)} require at least n(IC⁡μ(g,0)−o(1))n\bigl(\operatorname{IC}_{\mu}(g,0)-o(1)\bigr) bits of worst-case communication. Moreover, at zero communication, our explicit exponent for κ\kappa recovers the current best bound of Ref. [16].

Consequences. Theorem 1.1 has several consequences. The first consequence determines the exact asymptotic distributional communication complexity of a finite total relation gg. For a fixed 0<ε<10<\varepsilon<1, let Dμ⊗n,ε(gn)D_{\mu^{\otimes n},\varepsilon}(g^n) denote the distributional communication complexity of gng^n under μ⊗n\mu^{\otimes n} with error at most ε\varepsilon; see § 3 for the formal definition. Theorem 1.1 rules out every fixed rate below IC⁡μ(g,0)\operatorname{IC}_{\mu}(g,0), since the success probability eventually falls below 1−ε1-\varepsilon. Conversely, applying the compression result of Ref. [4] to independent executions of a zero-error protocol achieves every fixed rate above IC⁡μ(g,0)\operatorname{IC}_{\mu}(g,0) with vanishing overall error. Therefore,

lim⁡n→∞Dμ⊗n,ε(gn)n=IC⁡μ(g,0).(1)\lim_{n\to\infty}\frac{D_{\mu^{\otimes n},\varepsilon}(g^n)}{n}=\operatorname{IC}_{\mu}(g,0). \tag*{(1)}

Thus, the asymptotic communication rate is independent of the fixed error allowance ε∈(0,1)\varepsilon\in(0,1) and is determined by the zero-error information complexity. Corollary 8.2 gives the full statement and proof.

Our result also has consequences for randomized communication complexity. Let IC⁡(g,0)\operatorname{IC}(g,0) denote the maximum of IC⁡μ(g,0)\operatorname{IC}_{\mu}(g,0) over all input distributions μ\mu. By definition, for every 0≤R<IC⁡(g,0)0\le R<\operatorname{IC}(g,0), there is an input distribution μ\mu such that R<IC⁡μ(g,0)R<\operatorname{IC}_{\mu}(g,0). Thus, applying the main theorem then gives exponential decay of the success probability when inputs are averaged over μ⊗n\mu^{\otimes n}, which gives the desired exponential decay of success probability on at least one input. See Corollary 8.3 for a formal statement.

Additionally, combining this exponential decay with the upper bound of Ref. [26] determines the asymptotic randomized communication rate exactly. For a fixed 0<ε<10<\varepsilon<1, let Rε(gn)R_{\varepsilon}(g^n) denote the randomized communication complexity of gng^n with error at most ε\varepsilon, as defined in § 3. As in the derivation of Equality (1), the implication for the randomized communication rules out every fixed rate below IC⁡(g,0)\operatorname{IC}(g,0) for all sufficiently large nn. Together with the upper bound [26], this establishes

lim⁡n→∞Rε(gn)n=IC⁡(g,0).\lim_{n\to\infty}\frac{R_{\varepsilon}(g^n)}{n}=\operatorname{IC}(g,0).

See Corollary 8.4 for the full statement and proof.

Prior works

We compare our results with earlier communication direct-product theorems, strong converses, and characterizations of amortized communication complexity, explaining which communication thresholds were previously known and which are determined by our theorem.

Direct product theorems. We first compare our result with earlier strong2 direct-product theorems [6, 21, 7 Yu22, 18] in communication complexity. For example, for a Boolean function gg under an arbitrary input distribution μ\mu, Ref. [6] proves exponentially small success whenever ∣Πn∣≥2|\Pi_n| \ge2 and

∣Πn∣(log⁡∣Πn∣)3/2<c(Dμ(g,1/3)−2)n.|\Pi_n|(\log|\Pi_n|)^{3/2} < c(D_\mu(g,1/3)-2)\sqrt{n}.

where ∣Πn∣|\Pi_n| is the worst-case communication cost of Πn\Pi_n and c>0c > 0 is a sufficiently small universal constant. More recently, Ref. [18] proves stronger results, known as XOR lemmas, and derives corresponding direct-product bounds, with a similar n\sqrt{n} dependence on the number of instances up to logarithmic factors.

As a prior work using internal information complexity IC⁡μ(g,1/3)\operatorname{IC}_\mu(g,1/3) with error ≤1/3\le1/3, Ref. [7] proves exponentially small success probability whenever ∣Πn∣≥2|\Pi_n| \ge2 and

∣Πn∣log⁡(∣Πn∣log⁡∣Πn∣)≤cnIC⁡μ(g,1/3),|\Pi_n|\log(|\Pi_n|\log|\Pi_n|) \le cn\operatorname{IC}_\mu(g,1/3),

again for a sufficiently small universal constant c>0c > 0. Ref. [3] also discusses the relation between parallel repetition and information complexity but without communication.

These results do not determine the optimal communication threshold for exponential decay for general tasks. In contrast, Theorem 1.1 establishes exponential decay at every fixed rate below IC⁡μ(g,0)\operatorname{IC}_\mu(g,0) for every finite total relation gg and arbitrary input distribution μ\mu, giving the exact threshold for the first time together with the matching upper bound discussed above.

Additionally, combining our theorem with the lower bounds on IC⁡μ(g,0)\operatorname{IC}_\mu(g,0) of Refs. [9, 20, 8] recovers several strong direct-product conclusions. Examples include those for Set Disjointness, Tribes, and Inner Product previously obtained in Refs. [22, 15, 23], respectively.

Works from information theory. Our result is also closely related to work in information theory, where such exponential decay of success is studied under the name of exponential strong converses. For a function gg, Ref. [TVVW17] proves, among other results, that for every fixed δ>0\delta> 0, the success probability of Πn\Pi_n is exponentially small whenever

∣Πn∣≤n[H(g(X,Y)∣X)+H(g(X,Y)∣Y)−δ].|\Pi_n| \le n\left[H(g(X,Y)\mid X)+H(g(X,Y)\mid Y)-\delta\right].

where (X,Y)∼μ(X,Y) \sim\mu and H(⋅∣⋅)H(\cdot\mid\cdot) denotes conditional entropy. Notably, Ref. [TVVW17] explicitly identifies replacing this entropy threshold by zero-error information complexity IC⁡μ(g,0)\operatorname{IC}_\mu(g,0) as the desired strengthening. The function case of Theorem 1.1 achieves this strengthening.

Refs. [TW20, HWS24] provide further close comparisons: they establish exponential strong converses with a fixed number of communication rounds, at the corresponding round-restricted rates. Our result has no restriction on the number of rounds.

Amortized communication complexity. Information complexity also characterizes amortized communication under a per-coordinate error requirement. Ref. [4] shows that IC⁡μ(g,ε)\operatorname{IC}_\mu(g,\varepsilon) equals the amortized distributional communication complexity when the error probability on each coordinate is at most ε\varepsilon. Ref. [5] establishes the corresponding characterization of randomized communication in terms of IC⁡(g,ε)\operatorname{IC}(g,\varepsilon). Under a strict requirement that all coordinates be correct simultaneously, Ref. [26] proves that, for every fixed 0<ε<10 < \varepsilon< 1, the amortized rate is exactly (1−ε)IC⁡(g,0)(1-\varepsilon)\operatorname{IC}(g,0) when communication cost is measured in expectation. For worst-case randomized communication complexity, Ref. [26] establishes the bounds

(1−ε)IC⁡(g,0)≤lim inf⁡n→∞Rε(gn)n≤lim sup⁡n→∞Rε(gn)n≤IC⁡(g,0).(1-\varepsilon)\operatorname{IC}(g,0) \le\liminf_{n\to\infty}\frac{R_\varepsilon(g^n)}{n} \le\limsup_{n\to\infty}\frac{R_\varepsilon(g^n)}{n} \le\operatorname{IC}(g,0).

Our result closes this interval at its upper bound and, more strongly, proves exponential decay of success probability at every rate below that value.

Proof techniques and comparison

We briefly outline our proof strategy to prepare for the comparison with prior techniques below; Section 3 gives a detailed proof overview using the terminology and notation introduced in Section 2.

References

  1. [1]Mohammad A. Alhejji and Graeme Smith. A tight uniform continuity bound for equivocation. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 2270–2274. IEEE, 2020.DOI
  2. [2]Mark Braverman, Ankit Garg, Denis Pankratov, and Omri Weinstein. From information to exact communication. In 45th annual Symposium on Theory of computing, pages 151–160, 2013.
  3. [3]Mark Braverman and Young K Ko. Information value of two-prover games. In 9th Innovations in Theoretical Computer Science Conference, 2018.
  4. [4]Mark Braverman and Anup Rao. Information equals amortized communication. In 52nd annual Symposium on Foundations of Computer Science, pages 748–757, 2011.
  5. [5]Mark Braverman. Interactive information complexity. SIAM Review, 59(4):803–846, 2017.
  6. [6]Mark Braverman, Anup Rao, Omri Weinstein, and Amir Yehudayoff. Direct products in communication complexity. In 54th Annual Symposium on Foundations of Computer Science, pages 746–755, 2013.
  7. [7]Mark Braverman and Omri Weinstein. An interactive information odometer and applications. In 47th annual symposium on Theory of Computing, pages 341–350, 2015.DOI
  8. [8]Mark Braverman and Omri Weinstein. A discrepancy lower bound for information complexity. Algorithmica, 76(3):846–864, 2016.
  9. [9]Ziv Bar-Yossef, T.S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. Journal of Computer and System Sciences, 68(4):702–732, 2004.
  10. [10]Imre Csiszár and János Körner. Information theory: coding theorems for discrete memoryless systems. Cambridge University Press, 2011.
  11. [11]Thomas M Cover and Joy A Thomas. Elements of information theory, 1991.
  12. [15]Prahladh Harsha and Rahul Jain. A Strong Direct Product Theorem for the Tribes Function via the Smooth-Rectangle Bound. In Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013), volume 24, pages 141–152, 2013.DOI
  13. [16]Thomas Holenstein. Parallel repetition: simplifications and the no-signaling case. In 39th annual symposium on Theory of computing, pages 411–419, 2007.
  14. [18]Siddharth Iyer and Anup Rao. Xor lemmas for communication via marginal information. In 56th Annual Symposium on Theory of Computing, pages 652–658, 2024.arxiv.org/abs/2312.03076
  15. [19]Rahul Jain and Srijita Kundu. A direct product theorem for quantum communication complexity with applications to device-independent QKD. In 62nd annual Symposium on Foundations of Computer Science, pages 1285–1295, 2022.
  16. [20]T. S. Jayram, Ravi Kumar, and D. Sivakumar. Two applications of information complexity. In 35th Annual Symposium on Theory of Computing, pages 673–682, 2003.
  17. [21]Rahul Jain, Attila Pereszlényi, and Penghui Yao. A direct product theorem for the two-party bounded-round public-coin communication complexity. In 53rd annual Symposium on Foundations of Computer Science, pages 167–176, 2012.
  18. [22]Hartmut Klauck. A strong direct product theorem for disjointness. In 42nd annual symposium on Theory of computing, pages 77–86, 2010.arxiv.org/abs/0908.2940
  19. [23]Troy Lee, Adi Shraibman, and Robert Špalek. A direct product theorem for discrepancy. In 23rd annual Computational complexity conference, pages 71–80, 2008.DOI
  20. [24]Ran Raz. A parallel repetition theorem. SIAM Journal on Computing, 27(3):763–803, 1998.
  21. [25]Anup Rao and Amir Yehudayoff. Communication Complexity: and Applications. Cambridge University Press, 2020.
  22. [26]Daiki Suruga. Zero-error information equals amortized communication complexity. arXiv preprint arXiv:2608.04141, 2026. (To appear in FOCS 2026).arxiv.org/abs/2608.04141
  23. [27]Pachara Sawettamalya and Huacheng Yu. Strong xor lemma for information complexity. In 57th Annual Symposium on Theory of Computing, pages 1626–1637, 2025.arxiv.org/abs/2411.13015

Paper details

vlnc:W_bv69wq26
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT

View statement
Looking for related papers…
Contents