- Time
- 1:30 – 2:20pm, Tuesday, January 12, 2010
- Place
- CSE 305
- Speaker
- Anup Rao, University of Washington
## Abstract

We describe new ways to simulate 2-party communication protocols to
get protocols with potentially
smaller communication. We show that every communication protocol that
communicates C bits and
reveals I bits of information to the participating parties can be
simulated by a new protocol
involving about sqrt(CI) bits of communication. In the case that the
parties have
inputs that are independent of each other, we get much better results,
showing how to carry out the
simulation with about O(I) bits of communication.

These results lead to a direct sum theorem for randomized
communication complexity. Ignoring
polylogarithmic factors, we show that for worst case computation,
computing n copies of a
function requires sqrt(n) times the communication required for
computing one copy of the
function.

As far as we know, our results give the first compression schemes for
general randomized protocols
and the first direct sum results in the general setting. Previous
results applied only when the
protocols were restricted to running in a constant number of rounds,
where each message can be
compressed in turn, and only applied when the parties are given
independent inputs.