Sem: Communication Complexity

2 Credits · Level: Graduate

Communication complexity studies how much information must be transmitted between two or more parties, who wish to jointly compute a function where the input is distributed between the parties. The most basic model of communication complexity was introduced by Yao in 1979, and is one of the few models in which we know strong unconditional lower bounds. Communication complexity provides a framework for proving lower bounds in several areas such as data structures, circuit complexity, streaming algorithms, etc. We will spend the first few weeks of the course covering basic techniques for proving lower bounds in the deterministic, non-deterministic and randomized models of communication complexity. These techniques are typically combinatorial, algebraic or information theoretic. After this, we will have paper presentations with the goal of understanding recent developments and open problems in the area.