Communication Complexity (for Algorithm Designers)
by Tim Roughgarden
Publisher: Stanford University 2015
Number of pages: 150
Description:
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; 2. Learn how to reduce lower bounds for fundamental algorithmic problems to communication complexity lower bounds.
Download or read it online for free here:
Download link
(2.8MB, PDF)
Download mirrors:
Mirror 1
Similar books
Think Complexity: Complexity Science and Computational Modelingby Allen B. Downey - Green Tea Press
This book is about complexity science, data structures and algorithms, intermediate programming in Python, and the philosophy of science. The book focuses on discrete models, which include graphs, cellular automata, and agent-based models.
(10079 views)
Measure-Preserving Systemsby Karl Petersen - University of North Carolina
These notes provide an introduction to the subject of measure-preserving dynamical systems, discussing the dynamical viewpoint; how and from where measure-preserving systems arise; the construction of measures and invariant measures; etc.
(11444 views)
Introduction to Computational Complexityby Martin Tompa
Lecture notes for a graduate course on computational complexity taught at the University of Washington. Alternating Turing machines are introduced very early, and deterministic and nondeterministic Turing machines treated as special cases.
(10393 views)
Algorithmic Randomness and Complexityby R. G. Downey, D. R. Hirschfeldt - Springer
Computability and complexity theory are two central areas of research in theoretical computer science. This book provides a systematic, technical development of algorithmic randomness and complexity for scientists from diverse fields.
(10800 views)