Information Equals Amortized Communication

Speaker: 

Time: 

Tuesday, 12 February 2019, 16:00 to 17:00

Venue: 

  • A-201 (STCS Seminar Room)

Organisers: 

Abstract: We will discuss Braverman and Rao's result that shows that the internal communication cost is same as the amortized communication complexity. The proof of the result uses a sampling protocol, which I feel is interesting in itself. The topic requires little background in information theory or communication complexity.