Communication Complexity 16:198:671

Meetings Tuesdays 5-8pm, Hill 254.
Instructor: Troy Lee
Office Hours: Wednesdays 4-5pm, Hill 415
Brief Course Description: Communication complexity studies how much two parties need to communicate in order to compute a function whose output depends on information distributed over both parties. This simple mathematical model allows communication complexity to be applied in many different situations, and it has become an essential component in the theoretical computer science toolbox.

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.


The grade for the couse will be based on problem sets (given every other week) and the writing of scribe notes. Problem sets are due at the beginning of the following class. Working in groups is permitted as long as you write up the solutions yourself. Late homework will only be accepted with prior consent of the instructor.


There is no required textbook for the course. A great supplementary reference is the book Communication Complexity by Kushilevitz and Nisan (abbreviated [KN] below). Another text we will make reference to is the survey article "Lower bounds in communication complexity" by Lee and Shraibman (denoted [LS] below).

Class Schedule:

Here is the Tex template for scribe notes.

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 communication complexity.
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."