Thin matrix products up to D <= N^0.172 and lossless reductions for 3SUM, Exact Triangle and APSP, with 3SUM over abelian groups and a dichotomy for coordinatewise problems
Ruhollah Majdoddin
cs.DS
Oct 12, 2026 · v1
TL;DR
Most of the paper's mathematics, including algorithm correctness, counts, exponents and the dichotomy theorem, is formalised in Lean 4 with Mathlib in a public repository.
Abstract
Alman and Vassilevska Williams (arXiv:2610.06783) gave the first polynomial improvements over the textbook algorithms for 3SUM and APSP: deterministic algorithms with exponents 1.9992 for 3SUM, 2.9983 for Exact Triangle and 2.99942 for APSP. Their algorithm has two steps: a matrix theorem, computing N^2/sqrt(D) prescribed entries of the product of an N x D and a D x N integer matrix in time N^2/D^gamma, gamma > 0, when D <= N^eps, for every eps < 0.1204; and reductions from the three problems to the lopsided sparse triangle problem. We improve both. With Schönhage's five-term partial-product tensor, the matrix theorem holds for every eps < 0.172. The preprint's reductions keep a quarter of the matrix theorem's saving for 3SUM and a half for Exact Triangle and APSP; ours keep all of it, by calling the counting version of the triangle problem adaptively and building composite moduli one prime at a time. Together this gives deterministic 3SUM in n^{1.9945+o(1)}, and Exact Triangle, (min,+)-product and APSP in n^{2.9945+o(1)}. We also improve on the preprint's proof sketch for 3XOR and solve it deterministically in O(n^{1.99451}). Which other problems on three lists does the method make truly subquadratic? It solves 3SUM over F_p^d for every fixed prime p with 3XOR's exponents, and over every finite abelian group of exponent p^2, such as Z_4^d, in O(n^{1.99726}). For coordinatewise problems with a fixed relation P on every coordinate triple, a certified exhaustive computation shows that every Boolean P, and every functional P over three letters, either is the solution set of an equation over Z, F_2 or F_3, and the problem is then truly subquadratic, or has a gadget for Orthogonal Vectors, and the problem is then hard under the Orthogonal Vectors hypothesis. Over four letters, just four functional relations, up to symmetry, satisfy neither condition.
Problem
Alman and Vassilevska Williams gave the first polynomial improvements over the textbook algorithms for 3SUM, Exact Triangle and APSP. Their method has two parts: a matrix theorem valid for D <= N^eps with eps < 0.1204, and reductions that lose a constant fraction of the saving. The question is whether both parts can be improved, and which other three-list problems the method reaches.
Approach
Schönhage's ten-term identity is replaced by Schönhage's five-term partial-product tensor, combined with F_2 re-indexing maps and a squared-run construction, which extends the matrix theorem to eps < 0.172. The reductions are made lossless by calling the counting triangle problem adaptively and building composite moduli one prime at a time. The method is extended to 3XOR, to 3SUM over F_p^d and over abelian groups of exponent p^2, and to coordinatewise problems through a certified exhaustive computation. Python scripts and a Lean 4 formalisation give machine checks.
Results
Deterministic 3SUM runs in n^{1.9945+o(1)}, and Exact Triangle, (min,+)-product and APSP run in n^{2.9945+o(1)}. A dichotomy shows that every Boolean, and every three-letter functional, coordinatewise relation is either an equation over Z, F_2 or F_3 (truly subquadratic) or Orthogonal-Vectors-hard. Over four letters, only four functional relations up to symmetry satisfy neither condition.
| Problem | [AV26] | Part I alone | Part II alone | Parts I and II |
|---|
| 3SUM | O(n^1.9992) | O(n^1.99863) | n^(1.99650+o(1)) | n^(1.99450+o(1)) |
| Exact Triangle | O(n^2.9983) | O(n^2.9973) | n^(2.99650+o(1)) | n^(2.99450+o(1)) |
| APSP | O(n^2.99942) | O(n^2.99909) | n^(2.99650+o(1)) | n^(2.99450+o(1)) |
| 3XOR | O(n^1.9992)† | O(n^1.99863)† | O(n^1.99651) | O(n^1.99451) |
Exponents compared with [AV26]