In this course, we will cover the basic results of communication complexity and bring students up to the frontier of open problems. We will discuss communication protocols using different resources--- deterministic, nondeterministic, randomized, and multiparty models--- and the relationship between these models. A large part of the course will focus on showing lower bounds in these models, i.e. showing that certain functions cannot be computed without a lot of communication. The application of communication complexity lower bounds to other computational models such as circuit complexity, proof complexity, and streaming complexity will also be discussed.
January 19: Deterministic Communication Complexity. Rectangle and
Log rank bounds. Application to formula size: Karchmer-Wigderson Game.
Supplementary Reading: [KN] pages 3--10, 13--15, 119--124. [LS] pages 14--20.
Lecture 1 scribe notes.
January 26: Nondeterministic Communication Complexity. Rectangle covers.
Relationship to deterministic complexity. Linear programming characterization.
Supplementary Reading: [KN] pages 16--27. [LS] pages 31--38.
Problem Set 1 out. Due February 2.
Lecture 2 scribe notes.
February 2: Randomized communication complexity. Definition of model,
Public coin vs. private coin, protocol for equality function.
Supplementary Reading: [KN] pages 28--40. [LS] pages 20--30, 39--57. A recent paper by Rahul Jain and Hartmut Klauck, The partition bound for classical communication and query complexity.
Problem Set 1 due.
February 9: Linear programming lower bounds, approximate norms, lower bound
for inner product.
Problem Set 2 out. Due February 16.
Lecture 4 scribe notes.
February 16: Yao's minimax principle, use of duality.
Problem Set 2 due.
Lecture 5 scribe notes.
February 23: Guest lecture Nikos Leonardos. Information theory lower bounds,
lower bound for disjointness.
Lecture 6 scribe notes.
March 2: Application of disjointness problem to streaming lower bounds
(including Alon, Matias, Szegedy application to frequency moments).
Lower bound for lopsided disjointness problem.
Lecture 7 scribe notes.
March 9: Guest lecture Mihai Patrascu. Data structure lower bounds from
Lecture 8 scribe notes.
March 16: No class, spring recess.
March 23: Quantum communication complexity. Quantum Basics, teleportation, and XOR games.
March 30: Quantum communication complexity continued. Lower bounds from XOR bias upper bounds, generalized discrepancy method.
April 6: Lower bounds for composed functions. Method of Sherstov and Shi-Zhu relating approximate degree to communication complexity.
April 13: Recap of pattern matrix method. Beginning Number-on-the-forehead
model. Grolmusz upper bound on NOF complexity of symmetric functions.
Lecture 12 scribe notes.
April 20: Number-on-the-forehead lower bounds. Babai-Nisan-Szegedy technique for upper bounding discrepancy, lower bounds for generalized inner product and disjointness.
April 27: Applications to proof complexity. We will follow the paper "Hardness escalation in proof complexity."