TLDR Tech / News
Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs
Researchers present the first polynomial improvements over textbook algorithms for 3SUM and All-Pairs Shortest Paths, deterministically solving 3SUM on $n$ integers in $O(n^{1.9992})$ time and APSP on directed $n$-vertex graphs in $O(n^{2.9995})$ time. These findings refute the 3SUM and APSP hypotheses, along with several other related rectangular matrix-vector conjectures and triangle hypotheses. The improvements follow from a single new algorithm for thin matrix products, which computes specified entries of matrix products in operations fewer than needed for the full matrix.
Read the full story