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

**Introduction to Computational Complexity**

by

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

(

**8080**views)

**P, NP, and NP-Completeness: The Basics of Complexity Theory**

by

**Oded Goldreich**-

**Cambridge University Press**

The main focus of the current book is on the P-vs-NP Question and the theory of NP-completeness. Additional topics that are covered include the treatment of the general notion of a reduction between computational problems.

(

**7515**views)

**Foundations of Cryptography**

by

**Oded Goldreich**-

**Cambridge University Press**

The book gives the mathematical underpinnings for cryptography; this includes one-way functions, pseudorandom generators, and zero-knowledge proofs. Throughout, definitions are complete and detailed; proofs are rigorous and given in full.

(

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

(

**9665**views)