Lecture Notes on Computational Complexity
by Luca Trevisan
Number of pages: 171
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:
by Oded Goldreich - 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.
by Allen B. Downey - Green Tea Press
This book is about complexity science, data structures and algorithms, intermediate programming in Python, and the philosophy of science. The book focuses on discrete models, which include graphs, cellular automata, and agent-based models.
by R. G. Downey, D. R. Hirschfeldt - 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.
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.