Computational Intractability:
A Guide to Algorithmic Lower Bounds

by Erik D. Demaine, William Gasarch, and Mohammad Hajiaghayi
MIT Press, 2024
Book Draft
View Book Draft (PDF)

Last updated: Saturday, April 8, 2023

This is a draft of the book. There will be typos, missing references, rough/missing figures, and other mistakes. Please help us find them!

Send comments and suggestions for improvements to


Copyright in this work has been licensed exclusively to The MIT Press, which will be releasing the final version to the public in 2024. All inquiries regarding rights should be addressed to the MIT Press, Rights and Permissions Department.

Video lectures about some of this book's material are available from the related class at MIT, Algorithmic Lower Bounds: Fun with Hardness Proofs.