How to Compress Interactive Communication

1:30 – 2:20pm, Tuesday, January 12, 2010
CSE 305
Anup Rao, University of Washington


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.