Abstract

Communication complexity can be viewed as the “master model” for proving lower bounds on discrete models. Reductions show that lower bounds on communication complexity give lower bounds on boolean circuits, data structures, algorithms in distributed computing, proof complexity, branching programs, Ramsey theory...after more than 3 decades of work, this list is still growing every year. We will give a quick introduction to the basic model of communication, see some examples of how it is connected to other models of computation, and discuss some of the major open questions in communication complexity.

Video Recording