CSE 291, Communication Complexity, Winter 2026
Communication complexity is a computational model which captures communication bottlenecks in algorithm design. The model consists of two or more players, each having their own input.
The goal is to accomplish some distributed task based on the inputs, while minimizing communication. This model captures many real-life scenarios, such as time-space tradeoffs for data structures, streaming algorithms, sketching algorithms, sub-linear time algorithms, and many more. This class will cover both the theory of communication complexity, as well as some of the applications of it.
Information:
- Class Times: MW 10:30-11:50, CSE 4258
- Instructor: Shachar Lovett, Office hours: Wed 2-3pm, CSE 4234.
- TA: Farzan Byramji, Office hours: Wed 12-1pm, B240A.
- Piazza: We use Piazza for announcements, students questions and answers, and any other communication. Please sign up.
- Gradescope: We use Gradescope for homework submission and grading. To sign up please use code X82JKX.
Homework:
Lecture notes:
The lecture notes are on
Overleaf and will be updated throughout the quarter.
Topics:
- Deterministic protocols: model, examples, clique vs independent set, lower bound techniques, applications to time-space tradeoffs and formula depth lower bounds
- Non-deterministic protocols: model, examples, lower bound techniques, application to linear programming lower bounds
- Randomized protocols: private, public and distributional models, examples, lower bound techniques, application to streaming algorithms lower bounds
- Unbounded error protocols: model, connection to sign rank, Forster's lower bound techniques
- Multi-party protocols: number-in-hand and number-on-forehead models, connections of deterministic protocols to additive combinatorics and Ramsey theory, lower bounds for randomized protocols
Evaluation:
4 homework sets and a final project, each worth 20%. The homework sets are standard problem solving. The final project is to read a relevant paper and write a short
survey (6-10 pages) about it. Both the homework and the final project can be done individually or in pairs.
Textbooks:
There are several good textbooks on the topic:
- Communication Complexity: And Applications, by Rao and Yehudayoff [Amazon], early draft [pdf]: recent book, covers the basics and some applications
- Communication complexity for algorithm designers, by Roughgarden [pdf]: focus on applications, some of the core theory
- Communication complexity, by Kushilevitz and Nisan [Amazon]: older book, covers the basic theory and some older applications
There are also a few good surveys on some more specialized topics:
- The story of set disjointness, by Chattopadhyay and Pitassi [pdf]: many applications for set disjointness communication lower bound
- Lower Bounds in Communication Complexity, by Shraibman and Lee [pdf]: many lower bound techniques
- Complexity lower bounds using linear algebra, by Lokam: various lower bounds [pdf]: various lower bounds techniques
The following lecture notes from similar classes might also be useful:
- Pitassi (U. Toronto): [link]
- Sherstov (UCLA): [link]