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 third session of this talk will take place on Thursday, January 15 from 9:30 am – 10:30 am; the fourth session of this talk will take place on Friday, January 16 from 9:30 am – 10:30 am.

Video Recording