Subquadratic 3SUM and Subcubic APSP
8 hours ago
- The paper presents the first polynomial improvements over textbook algorithms for 3SUM and All-Pairs Shortest Paths (APSP), solving them in O(n^1.9992) and O(n^2.9995) time respectively.
- It refutes several hypotheses, including 3SUM, APSP, Exact Triangle, Zero-Weight k-Clique, and rectangular Online Matrix-Vector conjectures.
- The results stem from a new algorithm for thin matrix products that computes selected entries in O(N^2/D^0.063) time, polynomially faster than full computation.
- The algorithm modifies Coppersmith's rectangular matrix multiplication using Schönhage's ten-multiplication identity to handle only required operations.
- It solves the All-Edges Sparse Triangle problem in truly subquadratic time on sparse lopsided tripartite graphs, which reduces to Exact Triangle, 3SUM, and APSP.
- A data structure version supports queries for single entries of the matrix product not known in advance.