Comment

Comment by jltsiren

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.

parent jltsiren 27 days ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton