TLDR Tech / News
New algorithms achieve subquadratic 3SUM and subcubic APSP using graph triangles
Researchers Josh Alman and Virginia Vassilevska Williams have developed deterministic algorithms that outperform standard methods for the 3SUM and All-Pairs Shortest Paths (APSP) problems. Their work presents a 3SUM solution in O(n^1.9992) time and an APSP solution for directed graphs in O(n^2.9995) time, challenging existing assumptions. This progress stems from a novel algorithm for sparse matrix multiplication, which solves the All-Edges Sparse Triangle problem efficiently on certain sparse, unbalanced graphs.
Read the full story