Compressing Bounded-Round Communication

Video of this lecture

Topic:Compressing Bounded-Round Communication
Speaker:Mark Braverman
Affiliation:Microsoft Research New England
Date:Monday, April 5
Time/Room:11:15am - 12:15pm/S-101
Video Link:

In this talk we will present a near-optimal compression scheme for bounded-round randomized 2-party communication protocols. 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: This talk will be independent of Anup's talk.