Abstract

We will begin with a review of communication complexity and its applications. We will discuss information theoretic methods for showing lower bounds in communication complexity, and discuss in detail tools such as round elimination and information cost and message compression, leading to recent direct sum theorems.

The first session of this talk will take place on Tuesday, January 13 from 9:30 am – 10:30 am; the second session of this talk will take place on Wednesday, January 14 from 9:30 am – 10:30 am; the third session of this talk will take place on Thursday, January 15 from 9:30 am – 10:30 am.

Video Recording