(This post is written by Erik Demaine, William Gasarch, and Mohammad Hajiaghayi)
In 1979 Garey and Johnson published the classic
Computers and Intractability: A Guide to NP-Completeness
There has been A LOT of work on lower bounds since then.
Topics that were unknown in 1979 include
Parameterized Complexity,
Lower bounds on approximation,
Other hardness assumptions (ETH, 3SUM-conjecture, APSP-conjecture, UGC, Others),
Online Algorithms,
Streaming Algorithms,
Polynomial Parity Arguments,
Parallelism, and
Many new problems have been shown complete or hard in NP, PSPACE, and other classes.
Hence a sequel is needed. While it is impossible for one book to encompass all, or even a large fraction, of the work since then, we are proud to announce a book that covers some of that material:
Computational Intractability: A Guide to Algorithmic Lower Bounds
by Erik Demaine, William Gasarch, and Mohammad Hajiaghayi. MIT Press. 2024
See HERE for a link to a first draft.
We welcome corrections, suggestions and comments on the book. Either leave a comment on this blog post or emailing us at hardness-book@mit.edu