Comment by dgacmu

5 hours ago

It feels different to me from the CS side - this paper in particular feels likely to open up new research instead of closing it off, and I find that really exciting and a worthwhile use of AI. Showing that there's a (completely impractical but who's counting) algorithm better than the previously hypothesized lower bounds seems like the kind of thing that will inspire a scramble to keep beating it (and figure out the true lower bound). I give this one a thumbs up.

4 comments

dgacmu

Reply
jltsiren  41 minutes ago

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.

vatsachak  5 hours ago

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.

  • dgacmu  3 hours ago

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