CS369E: Communication Complexity (for Algorithm Designers) Lecture #1: Data Streams: Algorithms and Lower Bounds∗

This class is mostly about impossibility results — lower bounds on what can be accom-plished by algorithms. However, our perspective will be unapologetically that of an algo-rithm designer.1 We’ll learn lower bound technology on a “need-to-know ” basis, guided by fundamental algorithmic problems that we care about (perhaps theoretically, perhaps prac-tically). That said, we will wind up learning quite a bit of complexity theory — specifically, communication complexity — along the way. We hope this viewpoint makes this course and these notes complementary to the numerous excellent courses, books [10, 11], and surveys (e.g. [12, 13, 6, 15]) on communication complexity.2 The theme of communication complexity lower bounds also provides a convenient excuse to take a guided tour of numerous models, problems, and algorithms that are central to modern research in the theory of algorithms but missing from many algorithms textbooks: streaming algorithms, space-time trade-offs in data structures, compressive sensing, sublinear algorithms, extended formulations for linear programs, and more. Why should an algorithm designer care about lower bounds? The best mathematical researchers are able to work on an open problem simultaneously from both sides. Even if you have a strong prior belief about whether a given mathematical statement is true or false, failing to prove one direction usefully informs your efforts to prove the other. (And for most ∗ c©2015, Tim Roughgarden