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
Algorithms and Complexityby Herbert S. Wilf - AK Peters, Ltd.
An introductory textbook on the design and analysis of algorithms. Recursive algorithms are illustrated by Quicksort, FFT, and fast matrix multiplications. Algorithms in number theory are discussed with some applications to public key encryption.
(23657 views)
Measure-Preserving Systemsby Karl Petersen - University of North Carolina
These notes provide an introduction to the subject of measure-preserving dynamical systems, discussing the dynamical viewpoint; how and from where measure-preserving systems arise; the construction of measures and invariant measures; etc.
(12574 views)
Communication Complexity (for Algorithm Designers)by Tim Roughgarden - Stanford University
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.
(7931 views)
P, NP, and NP-Completeness: The Basics of Complexity Theoryby 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.
(11253 views)