Post

Truly subquadratic time for 3SUM is a problem I have thought about on and off for many years. Now a breakthrough result has been announced by Josh Alman and Virginia Vassilevska Williams! arxiv.org/abs/2610.06783

The significance of the result comes from the fact that many algorithms have time complexity that is linked to the time complexity of 3SUM via "fine grained" reductions. In addition to 3SUM the paper also breaks the cubic barrier for the all-pairs shortest path problem.

The algorithms were first discovered at Anthropic by an internal version of Claude, then digested and verified by the authors. Though there are questions one can ask about attribution and incentives, this strikes me as a better approach than just putting undigested AI-generated content online.