Comment by remywang
8 hours ago
3SUM is (was?) one of the key conjectures in fine-grained complexity, mostly used to derive lower bounds for other problems. As such, most did not think a subquadratic algorithm was possible. Similar for APSP
8 hours ago
3SUM is (was?) one of the key conjectures in fine-grained complexity, mostly used to derive lower bounds for other problems. As such, most did not think a subquadratic algorithm was possible. Similar for APSP
But from what I understand this doesn't refute SETH, no?
> But from what I understand this doesn't refute SETH, no?
SETH: Strong Exponential Time Hypothesis
See https://en.wikipedia.org/w/index.php?title=Exponential_time_...
No it does not.