Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics

The "short cycle removal" technique was recently introduced by Abboud, Bringmann, Khoury and Zamir (STOC '22) to prove fine-grained hardness of approximation. Its main technical result is that listing all triangles in an n 1/2 -regular graph is n 2-o(1) -hard even when the number of short cycles is small; namely, when the number of k-cycles is O(n k/2+γ ) for γ < 1/2. Its corollaries are based on the 3-SUM conjecture and their strength depends on γ, i.e. on how effectively the short cycles are removed.

Abboud et al. achieve γ ≥ 1/4 by applying structure versus randomness arguments on graphs. In this paper, we take a step back and apply conceptually similar arguments on the numbers of the 3-SUM problem, from which the hardness of triangle listing is derived. Consequently, we achieve the best possible γ = 0 and the following lower bound corollaries under the 3-SUM conjecture:

• Approximate distance oracles: The seminal Thorup-Zwick distance oracles achieve stretch 2k ±O(1)

after preprocessing a graph in O(mn 1/k ) time. For the same stretch, and assuming the query time is n o(1) Abboud et al. proved an Ω(m 1+ 1 12.7552•k ) lower bound on the preprocessing time; we improve it to Ω(m 1+ 1 2k ) which is only a factor 2 away from the upper bound. Additionally, we obtain tight bounds for stretch 2 + o(1) and 3 -ε and higher lower bounds for dynamic shortest paths.

• Listing 4-cycles: Abboud et al. proved the first super-linear lower bound for listing all 4-cycles in a graph, ruling out (m 1.1927 + t) 1+o(1) time algorithms where t is the number of 4-cycles. We settle the complexity of this basic problem by showing that the O(min(m 4/3 , n 2 ) + t) upper bound is tight up to n o(1) factors.

Our results exploit a rich tool set from additive combinatorics, most notably the Balog-Szemerédi-Gowers theorem and Rusza's covering lemma. A key ingredient that may be of independent interest is a truly subquadratic algorithm for 3-SUM if one of the sets has small doubling.