Source-linked AI summary
A simplified proof of polynomial improvements for 3SUM and APSP
Sankeerth Rao Karingula, Shachar Lovett
TL;DR
Integer 3SUM and APSP have truly subquadratic and subcubic algorithms, respectively, for polynomially bounded inputs. This paper simplifies the proof using recursive selected-entry matrix multiplication and Offline Set Disjointness, recovering the qualitative improvements with weaker exponents.
Problem
The paper addresses proving truly subquadratic integer 3SUM and truly subcubic APSP algorithms for polynomially bounded inputs.
Source: §1 · p. 1Method
It recursively applies selected-entry matrix multiplication and uses Offline Set Disjointness with existing deterministic reductions to reach 3SUM and APSP.
Source: §1.1 · p. 2Results
The proof recovers qualitative truly subquadratic 3SUM and truly subcubic APSP improvements for polynomially bounded inputs, with weaker exponents than the established algorithms.
Source: §1 · p. 1Takeaways & Limitations
The paper provides a simpler proof of these qualitative algorithmic improvements, prioritizing exposition over optimized constants.
Source: §1 · pp. 1–2The authors do not optimize constants, focusing instead on simplicity of exposition.
Source: §1 · p. 2
Abstract
from arXiv · showhide
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\"onhage'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.
1 Introduction
The paper gives a simpler, weaker-exponent proof of polynomial improvements for integer 3SUM and APSP. Its central tool is selected-entry matrix multiplication, applied through Offline Set Disjointness.
1 Introduction
- The proof recovers qualitative truly subquadratic integer 3SUM and truly subcubic APSP improvements for polynomially bounded inputs, with weaker exponents than Alman and Vassilevska Williams [1].The cited work established those improvements; this paper simplifies their proof.Source: §1 · pp. 1–2
1.1 Proof overview
- Incidence-matrix products encode set-intersection sizes, letting the algorithm solve Offline Set Disjointness before deterministic reductions connect it to 3SUM and APSP.The paper treats the existing reductions as black boxes.Source: §1 · p. 1, §1.1 · p. 2
1 Introduction
- Selected-entry matrix multiplication computes w specified entries of XY, avoiding both wd separate multiplications and the cost of writing the full product.The inputs are n × d and d × m matrices; the comparisons are wd multiplications and Ω(nm) time, respectively.Source: §1 · p. 1
- eO(n^2/d^1/4) time computes floor(n^2/d) specified entries when dκ+1 ≤ n, versus Θ(n^2) separate dot products and a full n^2-entry product.The passage says this yields a polynomial-factor saving when d is a fixed positive power of n.Source: §1 · p. 2
1.1 Proof overview
- The proof uses an exact rule with six shared products and one private correction per output, applies it recursively to blocks, and counts requests at each level.The request counts are capped by the available output positions; the sparse-output idea comes from Alman and Vassilevska Williams [1].Source: §1.1 · p. 2
- The open questions include reducing the d^τ loss without raising input-preparation costs or requiring thinner matrices, and extending savings to larger d.The paper also asks for simpler rules or different algorithms that achieve such savings.Source: §1.1 · pp. 2–3
2 Selected-entry matrix multiplication
This section develops a deterministic recursive algorithm for computing specified entries of a matrix product by reusing shared products and counting only the requests needed for those outputs, with a runtime bound and a density tradeoff. Its intermediate values remain small enough to use O(log(n + m)) bits.
2 Selected-entry matrix multiplication
- For integer k ≥ 81 with d^{6k} ≤ min{n,m}, matrices X ∈ Z^{n×d} and Y ∈ Z^{d×m} of polynomial-magnitude integer entries permit deterministic computation of any w ≥ 1 distinct specified entries of XY.Source: §2 · p. 3
2.1 The multiplication rule
- The multiplication rule reconstructs each output from six shared products minus one private product, with shared products reused across outputs.For the R × 2 by 2 × S rule, the common collection has 6k shared products; each shared product serves k outputs. The cancellation identity enables the shared construction.Source: §2.1 · pp. 4–5
2.2 The recursive computation
- Applying the rule to matrix blocks reduces the middle dimension by half, and each requested parent entry is recovered from six shared answers and one private answer.Repeated requests for the same entry in a child are merged, leaving exactly w private requests and at most 6w shared requests.Source: §2.2 · p. 8
- The recursive analysis bounds requests at each depth by both their generation count and the available output positions, then uses the smaller bound for each pattern.After t steps, the operation bounds include D3k(N + M) input-preparation additions and subtractions, B^t scalar multiplications, and O(tB^t) reconstruction operations.Source: §2.2 · pp. 8–9
- Each preparation or reconstruction step combines O(k) values, bounding intermediates by (6k)^O(t)L^2 and their bit length by O(log(n + m)).For fixed k, t = O(log d), and polynomially bounded L, this proves equation (2).Source: §2.2 · p. 10
3 Applications to fine grained algorithms
The section uses Offline Set Disjointness to connect selected incidence-matrix product entries with faster algorithms for 3SUM and APSP. It combines a small-universe algorithm with known deterministic reductions.
3 Applications to fine grained algorithms
- Incidence-matrix product entries give set-intersection sizes, so computing only queried entries determines whether each requested pair is disjoint.Source: §3 · p. 10, §3.1 · p. 10
3.1 Offline Set Disjointness
- For d^K ≤ n and w ≤ n^2/d, Offline Set Disjointness takes deterministic eO(n^2/d^1/8) time.Source: §3.1 · p. 10
3.2 Known reductions
- The 3SUM reduction uses O(n) sets, universe O(n^(2η)), set size O(n^η), and O(n^(2−η)) Offline Set Disjointness queries.Source: §3.2 · p. 11
- 3SUM takes deterministic eO(n^(2−η/4)) time, Exact Triangle eO(n^(3−ρ)), and APSP eO(n^(3−ρ/3)) time via deterministic reductions.Source: §3.2 · p. 11
- For APSP, Exact Triangle reduces to O(ng) set-disjointness instances with at most n^2/d queries each; choosing d=n^ε and g=⌈d^1/16⌉ yields a subcubic bound.Source: §3.2 · p. 11