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 introduce the basic concepts and techniques in communication complexity, as well as its motivations and its applications—to learning theory, data structures, circuit complexity, combinatorics, and so on. Theorems in communication complexity often have implications for the resources required in various models of computation, like streaming algorithms and query complexity, and for the structure of problems in learning theory.
While teaching the basic concepts and applications of communication complexity, the course will also emphasize the open problems: what we don’t know about communication and why it matters.
Prerequisites: This is a theory course, so “mathematical maturity” is necessary (meaning, basically, you are not scared of proofs).
Work in Progress...