Comment by akoboldfrying
1 hour ago
> It feels like that particular research direction is now a dead end
This is the most negative possible take on the most positive possible kind of result in CS.
To see just how unduly negative it is, imagine how different your response would have been had the exact same result been reported in a paper by exclusively human authors. Would you have likewise accused them of creating a research "dead end"?
EDIT: Changed "by, e.g., Ryan Williams" to "by exclusively human authors". Without having checked the authors, who include Ryan's wife and frequent collaborator Virginia, I had reached for a big name in the field purely as an example of a human who might well have made this breakthrough on their own.
There is a difference between one-off results and processes that can generate new results at an industrial scale.
Conditional lower bounds are a way of building understanding of the essential difficulty of specific computational problems. But if AI can now routinely generate marginal improvements, conditional bounds based on unproven assumptions become a waste of effort.
This is mostly due to how mathematics works. Ideally, we would like to prove something like "if problem A is essentially this difficult, problem B is essentially that difficult". But what we actually prove is more like "if (specific formulation of the difficulty of problem A), then (specific formulation of the difficulty of problem B)".
But those specific formulations become fixed targets for the AI to attack. If it manages to break the specific assumption, for example by creating an O(n^1.9998) time algorithm that is for all intents and purposes worse than a naive O(n^2) time algorithm, the conditional result becomes void. We could try to salvage the result with a different formulation, but that again becomes a fixed target.
This is essentially Goodhart's Law. We measure improvement with highly precise metrics, while we are actually interested in qualitative understanding.
Yeah, I can't get behind this. By showing one problem had an improved lower bound, they showed that another five algorithms could also be improved, and, yes, they refuted the 3SUM hypothesis and made a lot of conjectures about the hardness of some problems less certain, but now ... now we have to go figure those out more precisely. Which is great. It's progress! And all of the work put into those reductions was what made this one result topple five algorithms, so it's not like it's been wasted work.