Logo

Lecture Notes on Computational Complexity

Lecture Notes on Computational Complexity
by


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.

Home page url

Download or read it online for free here:
Download link
(0.9MB, PDF)

Similar books

Book cover: Foundations of CryptographyFoundations of Cryptography
by - Cambridge University Press
The book gives the mathematical underpinnings for cryptography; this includes one-way functions, pseudorandom generators, and zero-knowledge proofs. Throughout, definitions are complete and detailed; proofs are rigorous and given in full.
(8732 views)
Book cover: Computability and ComplexityComputability and Complexity
- Wikibooks
This book is intended as an introductory textbook in Computability Theory and Complexity Theory, with an emphasis on Formal Languages. Its target audience is CS and Math students with some background in programming and data structures.
(3618 views)
Book cover: Introduction to Computational ComplexityIntroduction to Computational Complexity
by
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.
(4836 views)
Book cover: Solving NP-Complete ProblemsSolving NP-Complete Problems
by - 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.
(3807 views)