ECCC-Report TR15-156https://eccc.weizmann.ac.il/report/2015/156Comments and Revisions published for TR15-156en-usMon, 28 Sep 2015 00:44:00 +0300
Paper TR15-156
| Communication Complexity (for Algorithm Designers) |
Tim Roughgarden
https://eccc.weizmann.ac.il/report/2015/156This 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.).Mon, 28 Sep 2015 00:44:00 +0300https://eccc.weizmann.ac.il/report/2015/156