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

by

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

(

**8278**views)

**Algorithmic Randomness and Complexity**

by

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

(

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

(

**8260**views)

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

(

**9689**views)