(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
Congratulations and appreciation to all three of you!
ReplyDelete- Jonathan Shewchuk
Looks like a well-done update of Garey & Johnson's 1979 classic. This was distinguished with a catalogue of all known NP-complete problems which the new version does not provide. Instead it focuses on well chosen examples and a broader up-to-date treatment of intractability. As a considerable amount of the content is referred to the exercises, there should be a solutions section which may at least contain a hint or a reference to the bibliography. I think Knuth, in his "The Art of Computer Programming," has done it in an exemplary way with his solutions to the excercises section. A rating of the difficulty of each excercise (another feature of Knuth's) is nice to have but not mandatory.
ReplyDeleteSome comments:
ReplyDelete-ABGS21 does not show 2^{(1-\eps)n} hardness for ShVecProb_p, but shows 2^{C_p n} hardness where the constant C_p grows with p, and C_p approaches 1 when p tends to infinity.
-The following statement is ambiguous. "This problem is the basis for many post-quantum crypto systems. Thats just a fancy way of saying crypto systems that do not depend on number-theoretic hardness assumptions." How would you define what a number-theoretic hardness assumption is? Why would, say, learning with errors not qualify?
Congratulations for your superb work!! Awaiting the book with impatience!!
ReplyDelete