Simplified proof improves key math problems with faster algorithms
A simplified proof of polynomial improvements for 3SUM and APSP
Computational Complexity
Summary
Some important math problems, like finding three numbers that add up to zero or calculating shortest paths in networks, usually take a long time to solve on computers. The authors present a simpler way to show that these problems can be solved faster than we thought, using clever math tricks involving multiplying parts of big tables of numbers. Their approach reduces the time for these problems when inputs are certain kinds of integers, helping algorithms run more quickly.
What this means in practice
- •For algorithm engineers: Design faster algorithms for integer 3SUM and all-pairs shortest paths by using improved matrix multiplication techniques.
- •For network designers: Improve shortest path computations in network routing when network data can be modeled with polynomially bounded integers.
A theory result. No direct application yet.
Authors
Sankeerth Rao Karingula, Shachar Lovett
Abstract
We give a simplified proof of the polynomial improvements for integer 3SUM and all-pairs shortest paths (APSP) established by Alman and Vassilevska Williams, with weaker exponents. The central ingredient is selected-entry matrix multiplication: computing a prescribed set of entries of a product of dense rectangular matrices. Starting from Schönhage's inner/outer-product identity, we construct a multiplication rule that shares intermediate products among many outputs. We apply this rule recursively and bound the work by counting the requested entries at each level. Applied to incidence matrices, the algorithm solves Offline Set Disjointness over a small universe. Known deterministic reductions then yield truly subquadratic integer 3SUM and truly subcubic APSP for polynomially bounded integer inputs.