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

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

(

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

(

**5548**views)

**Around Kolmogorov Complexity: Basic Notions and Results**

by

**Alexander Shen**-

**arXiv.org**

Algorithmic information theory studies description complexity and randomness. This text covers the basic notions of algorithmic information theory: Kolmogorov complexity, Solomonoff universal a priori probability, effective Hausdorff dimension, etc.

(

**764**views)

**Solving NP-Complete Problems**

by

**F. D. Lewis**-

**University of Kentucky**

This is an on-line textbook on heuristic algorithms. From the table of contents: Classes of Problems; Integer Programming; Enumeration Techniques; Dynamic Programming; Approximate Solutions; Local Optimization; Natural Models.

(

**4338**views)