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

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

2012-01-08

arxiv.org/abs/1201.1666v1

Computer Science

Computational Complexity

19 pages, version 1

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A direct product theorem for bounded-round public-coin randomized communication complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A direct product theorem for bounded-round public-coin randomized communication complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A direct product theorem for bounded-round public-coin randomized communication complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-641790