alt Hacker NewsIt 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.
Replies
vatsachak • yesterday at 7:20 PM
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.
➕ show 1 reply
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.