(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