| COMPUTER SCIENCE/DISCRETE MATH II | |
| Topic: | Direct Sums in Randomized Communication Complexity |
| Speaker: | Anup Rao |
| Affiliation: | Member, School of Mathematics |
| Date: | Tuesday, March 24 |
| Time/Room: | 10:30am - 12:30pm/S-101 |
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.