CSE 291, Communication Complexity, Winter 2019
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: M,W 11:00-12:20, EBU3B (CSE building), room 4258
- Instructor: Shachar Lovett, slovett@ucsd.edu, Office hours: Wednesdays 9-11am, CSE 4234
- TA: Sankeerth Rao, sankeerth1729@gmail.com, Office hours: Thursdays 9-11am, lobby next to CSE 4232
- Piazza: We use Piazza for announcements, students questions and answers, and any other communication: http://piazza.com/ucsd/winter2019/cse291b00. Please sign up.
Topics:
- Communication complexity models
- Lower bound techniques
- Applications
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 and surveys that we will partially follow:
- Communication complexity, by Kushilevitz and Nisan: covers a lot of classic material [Amazon]
- Communication complexity for algorithm designers, by Roughgarden: focuses on applications [pdf]
- The story of set disjointness, by Chattopadhyay and Pitassi: gives many applications for set disjointness communication lower bound [pdf]
- Communication complexity by Yehudayoff and Rao: covers more modern topics, still a work in progress [pdf]
- Lower Bounds in Communication Complexity, by Shraibman and Lee: many lower bound techniques [pdf]
- Complexity lower bounds using linear algebra, by Lokam: various lower bounds [pdf]
The following lecture notes from similar classes might also be useful:
- Pitassi (U. Toronto): [link]
- Sherstov (UCLA): [link]
Lecture notes:
Homework: