Wednesday, August 24, 2022

Computational Intractability: A Guide to Algorithmic Lower Bounds. First draft available! Comments Welcome!

(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



4 comments:

  1. Congratulations and appreciation to all three of you!
    - Jonathan Shewchuk

    ReplyDelete
  2. 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.

    ReplyDelete
  3. Some comments:
    -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?

    ReplyDelete
  4. Marios Mavronicolas10:55 PM, January 23, 2024

    Congratulations for your superb work!! Awaiting the book with impatience!!

    ReplyDelete