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: