Subquadratic 3SUM and Subcubic APSP

Researchers Josh Alman and Virginia Vassilevska Williams have achieved the first polynomial improvements over classical algorithms for the 3SUM problem and All-Pairs Shortest Paths (APSP), solving 3SUM in O(n^1.9992) time and APSP in O(n^2.9995) time. Their breakthrough stems from a new algorithm for sparse matrix multiplication that efficiently computes only required entries, refuting long-standing computational complexity hypotheses. The results also yield polynomial speedups for numerous related problems including exact triangle detection and various clique problems.