Rudich & Wigderson. Computational Complexity Theory
Three weeks of lectures from the IAS/Park City Mathematics Institute Summer School on computational complexity. Topics include reductions, lower-bounds, average-case complexity, randomness, interactive proof systems, probabilistically checkable proofs, quantum computing, and…
- from
- Theoretical Computer Science
- added
- 2026-10-10
- likes
- 0
similar
-
Goldreich. Computational Complexity: A Conceptual Perspective wisdom.weizmann.ac.il
A grad introduction to computation complexity theory, emphasizing the idea behind concepts of complexity theory.
-
-
Demaine, Gasarch & Hajiaghayi. Computers and Intractability: A Guide to Algorithmic Lower Bounds hardness.mit.edu
A sequel to Garey and Johnson's Computers and Intractability: A Guide to NP-Completeness. New topics include Parameterized Complexity, Lower bounds on approximation, Other hardness assumptions (ETH, 3SUM-conjecture, APSP-conjecture, UGC, Others), Online Algorithms, Streaming…
-
Arora & Barak. Computational Complexity: A Modern Approach theory.cs.princeton.edu
A golden standard textbook, Surveying computational complexity theory for graduate students and researchers.
-
Papadimitriou. Computational Complexity pearson.com
Body of knowledge for studying the performance and limitations of computer algorithms. Among topics covered are: reductions and NP-completeness, cryptography and protocols, randomized algorithms, and approximability of optimization problems, circuit complexity, the structural…
-
Walter Dean. Computational Complexity Theory and the Philosophy of Mathematics academic.oup.com
It highlights the significance of complexity theory relative to questions traditionally asked by philosophers of mathematics while also attempting to isolate some new ones.
Theoretical Computer Science › Computational Complexity > Introductory > Lecture Notes: “Three weeks of lectures from the IAS/Park City Mathematics Institute Summer School on computational complexity. Topics include reductions, lower-bounds, average-case complexity, randomness, interactive proof systems, probabilistically checkable proofs, quantum computing, and…”