Title: Direct Sums in Randomized Communication Complexity
Speaker: Anup Rao (Princeton)
Abstract:
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
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.
This is joint work with Boaz Barak, Mark Braverman and Xi Chen.