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