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: Algorithmic Randomness and ComplexityAlgorithmic Randomness and Complexity
by - 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.
(4468 views)
Book cover: Communication Complexity (for Algorithm Designers)Communication Complexity (for Algorithm Designers)
by - 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.
(715 views)
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.
(9537 views)
Book cover: Complexity and ComputationComplexity and Computation
by - Green Tea Press
This book is about data structures and algorithms, intermediate programming in Python, complexity science and the philosophy of science. The book covers Graphs, Analysis of algorithms, Scale-free networks, Cellular Automata, Agent-based models, etc.
(10420 views)