Compressing bounded-round communication

1:30 – 2:20pm, Tuesday, March 9, 2010
CSE 305
Mark Braverman, Microsoft Research - New England


In this talk we will present a near-optimal compression scheme for bounded-round randomized 2-party communication protocol. Previously, such a scheme was only known for protocols where the inputs to the parties are independent.

The results yield a new optimal direct sum theorem for bounded-round communication. They also reveal a tight connection between the Information Cost of a problem and its amortized Communication Complexity.

Joint work with Anup Rao. A talk by Anup on the prequel to this work can be found here: