New Algorithm Achieves Subquadratic 3SUM and Subcubic APSP Times, Refuting Hypotheses

Breakthrough in Algorithmic Efficiency

A new algorithm has achieved the first polynomial improvements for the 3SUM and All-Pairs Shortest Paths (APSP) problems. The 3SUM problem, involving finding three integers that sum to zero, can now be solved in O(n^1.9992) time. The APSP problem, which calculates the shortest paths between all pairs of vertices in a graph, can be solved in O(n^2.9995) time for directed graphs with polynomially bounded integer weights.

Refuting Long-Standing Hypotheses

These results directly refute the 3SUM and APSP hypotheses, which posited that these problems could not be solved in truly subquadratic or subcubic time, respectively. The new algorithm also refutes real-valued versions of these hypotheses, the Exact Triangle hypothesis, and the Zero-Weight k-Clique hypotheses. Additionally, it provides polynomial speedups for a variety of other related computational problems.

Underlying Algorithmic Innovation

The core of this breakthrough is a new algorithm for thin matrix products. Specifically, it computes entries of a product XY for an NxD matrix X and a DxN matrix Y (where D is significantly smaller than N) at specified positions in O(N^2/D^0.063) operations. This is a polynomial improvement over previous methods and is achieved by modifying a variant of Coppersmith's rectangular matrix multiplication algorithm.

Graph Theory Implications

Interpreted as a graph algorithm, this method solves the All-Edges Sparse Triangle problem in truly subquadratic time on sparse lopsided tripartite graphs. This is significant because problems like Exact Triangle, and by extension 3SUM and APSP, are known to reduce to this specific graph problem. The research also includes a data structure version for querying single entries of the matrix product.