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

by

**Oded Goldreich**

Complexity theory is the study of the intrinsic complexity of computational tasks. The book is aimed at exposing the students to the basic results and research directions in the field. The focus was on concepts, complex technical proofs were avoided.

(

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

(

**10216**views)

**Computability and Complexity from a Programming Perspective**

by

**Neil D. Jones**-

**The MIT Press**

The author builds a bridge between computability and complexity theory and other areas of computer science. Jones uses concepts familiar from programming languages to make computability and complexity more accessible to computer scientists.

(

**6681**views)

**Complexity Theory**

by

**Johan HÃ¥stad**

This set of notes gives the broad picture of modern complexity theory, defines the basic complexity classes, gives some examples of each complexity class and proves the most standard relations. The author emphasizes the ideas involved in the proofs.

(

**10969**views)