I find this thought funny: The faster the reduction, the stronger the lower bound.

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)

> 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!

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).

Nice. I'll definitely put it on my eReader.

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.

Really excited for this book. I would also recommend "The Nature of Computation" by Cristopher Moore and Stephan Mertens if you are interested in these topics.

It is really an underrated book and hands-down is the most enjoyable technical book that I have ever read.