**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

**Complexity Theory: A Modern Approach**

by

**Sanjeev Arora, Boaz Barak**-

**Cambridge University Press**

The book provides an introduction to basic complexity classes, lower bounds on resources required to solve tasks on concrete models such as decision trees or circuits, derandomization and pseudorandomness, proof complexity, quantum computing, etc.

(

**17578**views)

**Computational Complexity: A Conceptual Perspective**

by

**Oded Goldreich**-

**Cambridge University Press**

This book offers a comprehensive perspective to modern topics in complexity theory. It can be used as an introduction as either a textbook or for self-study, or to experts, since it provides expositions of the various sub-areas of complexity theory.

(

**11856**views)

**Complexity and Computation**

by

**Allen Downey**-

**Green Tea Press**

This book is about data structures and algorithms, intermediate programming in Python, complexity science and the philosophy of science. The book covers Graphs, Analysis of algorithms, Scale-free networks, Cellular Automata, Agent-based models, etc.

(

**15635**views)

**Lecture Notes on Computational Complexity**

by

**Luca Trevisan**

Notes from a graduate courses on Computational Complexity. The first 15 lectures cover fundamentals, the remaining is advanced material: Hastad's optimal inapproximability results, lower bounds for parity in bounded depth-circuits, and more.

(

**15101**views)