In any computation, information needs to go between different places. In Turing machines, it must be carried forward through time. In circuits, it must go across wires. Understanding how much information needs to go between different places is the subject of communication complexity, which boils down to: How much do two parties, Alice and Bob, need to communicate, in order to solve a problem?
This course will begin with the basics of communication complexity, its motivations and its applications—to data structures, circuit complexity, combinatorics, and so on. After that, the focus will be on the open problems: What don’t we know about communication complexity?
The structure of the course will be similar to a reading group: students will read papers and explain them to the class (with the instructor’s help). We will progress through several open problems and look at how the problem arises, why we care, and how people have approached it.
Prerequisites: 4th-year undergraduate theoretical computer science should be sufficient.
Work in Progress...