ECCC-Report TR09-044https://eccc.weizmann.ac.il/report/2009/044Comments and Revisions published for TR09-044en-usWed, 20 May 2009 11:33:28 +0300
Paper TR09-044
| Direct Sums in Randomized Communication Complexity |
Boaz Barak,
Mark Braverman,
Xi Chen,
Anup Rao
https://eccc.weizmann.ac.il/report/2009/044Does computing n copies of a function require n times the computational effort? In this work, we
give the first non-trivial answer to this question for the model of randomized communication
complexity.
We show that:
1. Computing n copies of a function requires sqrt{n} times the communication.
2. For average case complexity, given any distribution mu on inputs, computing n copies of the
function on n independent inputs sampled according to mu requires at least sqrt{n} times the
communication for computing one copy.
3. If mu is a product distribution, computing n copies on n independent inputs sampled according to
mu requires n times the communication.
We also study the complexity of computing the parity of n evaluations of f, and obtain results
analogous to those above.
Our results are obtained by designing compression schemes for communication protocols that can be
used to compress the communication in a protocol that does not transmit a lot of information about
its inputs.
Wed, 20 May 2009 11:33:28 +0300https://eccc.weizmann.ac.il/report/2009/044