upvote
This paper was more about closing off research, but in an amusing way.

There are a lot of results about conditional lower bounds: "If this problem is at least this hard, that other problem must be at least that hard." But now a widely used assumption was proven wrong, and an entire house of cards collapsed.

It feels like that particular research direction is now a dead end, until we can figure out a way of proving conditional bounds that is robust against technicalities. We would like to prove something like "If this problem is essentially at least this hard, that other problem must be essentially at least that hard." If the conditional bound depends on the assumption that the first problem requires at least n^2 time but somebody comes up with an O(n^1.9992) time algorithm, a slightly weaker conditional bound would still remain.

reply
Yeah but at least IMO TCS has little to do with real world optimization. Real world optimization uses the easiest possible algorithms with very simple ideas like min-cut flows.
reply
Absolutely! This is unlikely to directly, or even in the next 20 years, result in anything practical. But it has a very similar feel to Stothers' and then Virginia Williams' earlier improvement on matrix multiply, where his thesis and her first paper were followed by a dozen others finding ways to build on it after 20 years of seeing no progress on the problem at all. None of them have resulted in anything practical but who cares, really? Understanding the problem better is good and maybe some time in the next hundred years it'll result in an improvement in practice also. Or not. :)
reply
Nice. That's why I'm a former mathematician haha
reply