**Lecture Notes on Computational Complexity**

by Luca Trevisan

2004**Number of pages**: 171

**Description**:

These are notes from a graduate courses on Computational Complexity offered at the University of California at Berkeley. The first 15 lectures cover fundamental material. The remaining lectures cover more advanced material - there are lectures on Hastad's optimal inapproximability results, lower bounds for parity in bounded depth-circuits, lower bounds in proof-complexity, and pseudorandom generators and extractors.

Download or read it online for free here:

**Download link**

(0.9MB, PDF)

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

(

**6018**views)

**From Complexity to Creativity**

by

**Ben Goertzel**-

**Plenum Press**

This text applies the concepts of complexity science to provide an explanation of all aspects of human creativity. The book describes the model that integrates ideas from computer science, mathematics, neurobiology, philosophy, and psychology.

(

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

(

**7389**views)

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

(

**12587**views)