Communication Complexity is the mathematical investigation of a fundamental question: *If two or more people want to compute something about the information they possess, how long does their conversation need to be?*

The study of communication complexity has connected diverse areas of mathematics to practically motivated questions in computer science. Most notably, communication complexity provides the dominant methods to prove lower bounds on boolean circuits, data structures, streaming algorithms, and many other practically motivated computational models. These lower bounds are proved using results from analysis, geometry, algebra, combinatorics and probability.

This is an advanced topics class. In the first couple of weeks, we shall talk about the basic definitions and techniques available to reason about communication. The rest of the course will be structured around several open problems in communication complexity. For each open problem, we shall discuss relevant background, known results and failed attempts that have been made to solve them. Some of the open problems we shall talk about:

- The log-rank conjecture.
- Lower bounds in the Number-on-Forehead model and connections to Ramsey theory.
- Lower bounds on compressing interactive communication.
- Lower bounds on data structures.

A useful reference is this soon-to-be-published

textbook.

#### Logistics

- Professor: Anup Rao, TA: Sivaramakrishnan Natarajan Ramamoorthy.
- Time and Location: Mondays and Wednesdays at 10-11:20 in MGH 295.
- Work: The class will involve one project, involving presenting a paper to the rest of the class in collaboration with others in the class.