Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-044 | 6th May 2009 00:00

Direct Sums in Randomized Communication Complexity


Authors: Boaz Barak, Mark Braverman, Xi Chen, Anup Rao
Publication: 20th May 2009 11:33
Downloads: 4942


Does 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


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.

ISSN 1433-8092 | Imprint