Subquadratic 3SUM and Subcubic APSP
arxiv.org
arxiv.org
Apparently, an employee at Anthropic was trying to prove a hardness result in cryptography (average-case hardness of Zero-k-Clique), but Claude instead developed this algorithm.
Anthropic then shared the result with Josh Alman and Virginia Vassilevska Williams for verification, the authors of most recent breakthroughs in fast matrix multiplication. (They are shown in this cartoon: https://www.smbc-comics.com/comic/mathematicians)
As far as I can tell, the idea is to interpret rectangular matrix algorithms like Schonhage's as a tree, and then very carefully extract only some of the entries. This way you can compute N^2/√D positions of an (N×D)×(D×N) matrix multiplication in subquadratic time, O(N^2/D^0.063)
Are there any examples of this path being pursued?
Most of what the labs are pursuing with "Recursive Self Improvement" is basically improving the underlying algorithms.