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

Algorithmica

A Direct Product Theorem for Two-Party Bounded-Round Public-Coin Communication Complexity

Rahul Jain, Attila Pereszlényi, Penghui Yao

Published Dec 18, 2015• 10 citations
Publisher
DOI
10.1007/s00453-015-0100-0

Related papers

Direct Product Theorems for Communication Complexity via Subdistribution Bounds.

Rahul Jain, Hartmut Klauck, Ashwin Nayak

Electronic colloquium on computational complexity•Jan 1, 2007•3 citations

Public vs Private Coin in Bounded-Round Information

Mark Braverman, Ankit Garg

Lecture notes in computer science•Jan 1, 2014•55 citations

On public-coin zero-error randomized communication complexity

Ben Davis, Hamed Hatami, William Pires +2 more

Information Processing Letters•Jun 22, 2022•3 citations

A direct product theorem for bounded-round public-coin randomized communication complexity

Rahul Jain, Attila Pereszlényi, Penghui Yao

In this paper, we show a direct product theorm in the model of two-party bounded-round public-coin randomized communication complexity. For a relation f subset of X times Y times Z (X,Y,Z are finite sets), let R^{(t), pub}_e (f) denote the two-party t-message public-coin communication complexity of f with worst case error e. We show that for any relation f and positive integer k: R^{(t), pub}_{1 - 2^{-Omega(k/t^2)}}(f^k) = Omega(k/t (R^{(t), pub}_{1/3}(f) - O(t^2))) . In particular, it implies a strong direct product theorem for the two-party constant-message public-coin randomized communication complexity of all relations f. Our result for example implies a strong direct product theorem for the pointer chasing problem. This problem has been well studied for understanding round v/s communication trade-offs in both classical and quantum communication protocols. We show our result using information theoretic arguments. Our arguments and techniques build on the ones used in [Jain 2011], where a strong direct product theorem for the two-party one-way public-coin communication complexity of all relations is shown (that is the special case of our result when t=1). One key tool used in our work and also in [Jain 2011] is a message compression technique due to [Braverman and Rao 2011], who used it to show a direct sum theorem for the two-party bounded-round public-coin randomized communication complexity of all relations. Another important tool that we use is a correlated sampling protocol, which for example, has been used in [Holenstein 2007] for proving a parallel repetition theorem for two-prover games.

arXiv:1201.1666•Jan 8, 2012•14 citations

Communication Complexity in Algebraic Two-Party Protocols

Rafail Ostrovsky, William E. Skeith

Lecture notes in computer science•Jan 1, 2008•14 citations

A Direct Product Theorem for the Two-Party Bounded-Round Public-Coin Communication Complexity

Rahul Jain, Attila Pereszlényi, Penghui Yao

A strong direct product theorem for a problem in a given model of computation states that, in order to compute k instances of the problem, if we provide resource which is less than k times the resource required for computing one instance of the problem with constant success probability, then the probability of correctly computing all the k instances together, is exponentially small in k. In this paper, we consider the model of two-party bounded-round public-coin randomized communication complexity. We show a direct product theorem for the communication complexity of any relation in this model. In particular, our result implies a strong direct product theorem for the two-party constant-message public-coin randomized communication complexity of all relations. As an immediate application of our result, we get a strong direct product theorem for the pointer chasing problem. This problem has been well studied for understanding round v/s communication trade-offs in both classical and quantum communication protocols. Our result generalizes the result of Jain [2011] which can be regarded as the special case when t=1. Our result can be considered as an important progress towards settling the strong direct product conjecture for the two-party public-coin communication complexity, a major open question in this area. We show our result using information theoretic arguments. Our arguments and techniques build on the ones used in Jain~\cite{Jain:2011}. %, where a strong direct product theorem for the %two-party one-way public-coin communication complexity of all %relations is shown (that is the special case of our result when $t=1$). One key tool used in our work and also in Jain~\cite{Jain:2011} is a message compression technique due to Braver man and Rao~\cite{Braverman2011}, who used it to show a {\em direct sum} theorem in the same model of communication complexity as considered by us. Another important tool that we use is a correlated sampling protocol, which for example, has been used in Holenstein~\cite{Holenstein2007} for proving a parallel repetition theorem for two-prover games.

Annual Symposium on Foundations of Computer Science•Oct 1, 2012•33 citations
In this paper, we show a direct product theorm in the model of two-party bounded-round public-coin randomized communication complexity. For a relation f subset of X times Y times Z (X,Y,Z are finite sets), let R^{(t), pub}_e (f) denote the two-party t-message public-coin communication complexity of f with worst case error e. We show that for any relation f and positive integer k: R^{(t), pub}_{1 - 2^{-Omega(k/t^2)}}(f^k) = Omega(k/t (R^{(t), pub}_{1/3}(f) - O(t^2))) . In particular, it implies a strong direct product theorem for the two-party constant-message public-coin randomized communication complexity of all relations f. Our result for example implies a strong direct product theorem for the pointer chasing problem. This problem has been well studied for understanding round v/s communication trade-offs in both classical and quantum communication protocols. We show our result using information theoretic arguments. Our arguments and techniques build on the ones used in [Jain 2011], where a strong direct product theorem for the two-party one-way public-coin communication complexity of all relations is shown (that is the special case of our result when t=1). One key tool used in our work and also in [Jain 2011] is a message compression technique due to [Braverman and Rao 2011], who used it to show a direct sum theorem for the two-party bounded-round public-coin randomized communication complexity of all relations. Another important tool that we use is a correlated sampling protocol, which for example, has been used in [Holenstein 2007] for proving a parallel repetition theorem for two-prover games.
A strong direct product theorem for a problem in a given model of computation states that, in order to compute k instances of the problem, if we provide resource which is less than k times the resource required for computing one instance of the problem with constant success probability, then the probability of correctly computing all the k instances together, is exponentially small in k. In this paper, we consider the model of two-party bounded-round public-coin randomized communication complexity. We show a direct product theorem for the communication complexity of any relation in this model. In particular, our result implies a strong direct product theorem for the two-party constant-message public-coin randomized communication complexity of all relations. As an immediate application of our result, we get a strong direct product theorem for the pointer chasing problem. This problem has been well studied for understanding round v/s communication trade-offs in both classical and quantum communication protocols. Our result generalizes the result of Jain [2011] which can be regarded as the special case when t=1. Our result can be considered as an important progress towards settling the strong direct product conjecture for the two-party public-coin communication complexity, a major open question in this area. We show our result using information theoretic arguments. Our arguments and techniques build on the ones used in Jain~\cite{Jain:2011}. %, where a strong direct product theorem for the %two-party one-way public-coin communication complexity of all %relations is shown (that is the special case of our result when t=1t=1t=1). One key tool used in our work and also in Jain~\cite{Jain:2011} is a message compression technique due to Braver man and Rao~\cite{Braverman2011}, who used it to show a {\em direct sum} theorem in the same model of communication complexity as considered by us. Another important tool that we use is a correlated sampling protocol, which for example, has been used in Holenstein~\cite{Holenstein2007} for proving a parallel repetition theorem for two-prover games.