CS369E: Communication Complexity (for Algorithm Designers)

Instructor: Tim Roughgarden (Office hours: by appointment, Gates 474.)

Time/location: 10AM--Noon on Thursdays in Gates 100.

Course description: The best algorithm designers can prove both possibility and impossibility results --- both upper and lower bounds. For example, every serious computer scientist knows a collection of canonical NP-complete problems and how to reduce them to other problems of interest. Communication complexity offers a clean theory that is extremely useful for proving lower bounds for lots of different fundamental problems. The two biggest goals of the course are:
1. Learn several canonical problems that have proved the most useful for proving lower bounds (Disjointness, Index, Gap-Hamming, etc.).
2. Learn how to reduce lower bounds for fundamental algorithmic problems to communication complexity lower bounds.
Along the way, we'll also:
3. Get exposure to lots of cool computational models and some famous results about them --- data streams and linear sketches, compressive sensing, space-query time trade-offs in data structures, sublinear-time algorithms, and the extension complexity of linear programs.
4. Scratch the surface of techniques for proving communication complexity lower bounds (fooling sets, discrepancy bounds, corruption bounds).

Prerequisites: undergraduate algorithms (CS161, or equivalent) and mathematical maturity.

Course requirements: Occasional written exercises. Students taking the course for a letter grade should also give a 20-minute presentation on a research paper related to the course.

All lectures notes in one PDF

Lecture notes

Exercises: We'll be continually adding to the list here. (Most recent additions on 3/17/15.)

Detailed schedule and references:

Related courses: