Long-Standing 3SUM and APSP Conjectures Refuted by New Matrix Multiplication Algorithm
Subquadratic 3SUM and Subcubic APSP
Researchers present the first polynomial improvements over textbook algorithms for 3SUM and All-Pairs Shortest Paths, solving 3SUM on n integers in O(n^1.9992) time and APSP on directed graphs with polynomial weights in O(n^2.9995) time. This refutes the 3SUM and APSP hypotheses, along with several related conjectures. The breakthrough stems from a new algorithm for thin matrix products that exploits sparsity in lopsided graphs.
We give the first polynomial improvements over the textbook algorithms for 3SUM and All-Pairs Shortest Paths (APSP): we show how to deterministically solve 3SUM on n integers of polynomial size in O(n^1.9992) time and APSP on directed n-vertex graphs with polynomially bounded integer weights in O(n^2.9995) time.