Demaine, Gasarch & Hajiaghayi. Computers and Intractability: A Guide to Algorithmic Lower Bounds
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…
- from
- Theoretical Computer Science
- added
- 2026-10-10
- likes
- 0
similar
-
Demaine. Algorithmic Lower Bounds: Fun with Hardness Proofs ocw.mit.edu
A class taking a practical approach to proving problems can't be solved efficient.
-
Goldreich. P, NP, and NP-Completeness: The Basics of Computational Complexity wisdom.weizmann.ac.il
A very gentle introduction to some fundamental ideas of computational complexity like NP-completeness and P vs NP.
-
Rudich & Wigderson. Computational Complexity Theory ams.org
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…
-
Copeland, Posy & Shagrir (editors). Computability: Turing, Gödel, Church, and Beyond mitpress.mit.edu
Computer scientists, mathematicians, and philosophers discuss the conceptual foundations of the notion of computability as well as recent theoretical developments.
-
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…
-
Arora. Overcoming Intractability in Machine Learning cs.princeton.edu
A seminar course that will focus on the following phenomenon: many problems in machine learning are formally intractable (e.g., NP-hard). Nevertheless they are solved in practice by heuristics. Can we design algorithms with provable guarantees (running time, solution quality)?
Theoretical Computer Science › Lower Bounds > Books: “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…”