Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-156 | 21st September 2015 16:33

Communication Complexity (for Algorithm Designers)



This document collects the lecture notes from my course ``Communication Complexity (for Algorithm Designers),'' taught at
Stanford in the winter quarter of 2015. The two primary 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, corruption bounds, etc.).

ISSN 1433-8092 | Imprint