New Algorithm Breaks 50-Year Barriers for 3SUM and Shortest Paths
The paper presents the first polynomial-time improvements over textbook algorithms for two foundational problems: 3SUM (finding triples summing to zero) and All-Pairs Shortest Paths, achieving O(n^1.9992) and O(n^2.9995) respectively. This refutes long-standing complexity-theoretic hypotheses (3SUM, APSP, Exact Triangle, Zero-Weight k-Clique, and others) via a single new technique for computing selected entries of "thin" matrix products faster than writing out the full product, built by modifying Coppersmith's rectangular matrix multiplication method with a Schönhage identity. Twitter commentary highlighted the result as a major theoretical breakthrough, with some noting that other fine-grained complexity hypotheses (like SETH) may plausibly also fall, and discussing what made this problem especially tractable to the methods used. Several tweets also circulated claims that Anthropic's AI model helped discover the result while working on another problem, with human mathematicians subsequently formalizing it into the paper — a claim presented as discussion/rumor rather than something confirmed in the paper itself.
Discussion: 3 tweets from 3 authors · @say_cem, @OREAXEAX, @HighFreqAsuka