Computers and Intractability: A Guide to Algorithmic Lower Bounds
hardness.mit.edu
hardness.mit.edu
When you reduce all-pair-shortest-paths (assuming a cubic lower bound) to your problem in quadratic time, your problem has a lower bound of linear time. However, when you speed up the reduction to linear time, your lower bound is quadratic time!
This also applies to simulations of TMs. The faster the simulation, the sharper the complexity classes.
Thus, by making something faster, you can show that something else cannot be made faster anymore.
(Afaik this also applies to P vs NP: Find a fast enough algorithm to reduce an arbitrary problem in EXP to NP and you showed that P!=NP)
I think it seems funny because we often intuit that “lower is better” but when it comes to lower bounds higher is better (in the sense of tighter).
Just finished (the draft of) Computational Complexity: A Modern Approach
https://theory.cs.princeton.edu/complexity/book.pdf
I ought to buy the hardcover now, as I've read the free version from cover to cover.
It is really an underrated book and hands-down is the most enjoyable technical book that I have ever read.