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+gamma)) for gamma < 1/2. Its corollaries are based on the 3-SUM conjecture and their strength depends on gamma, i.e. on how effectively the short cycles are removed. Abboud et al. achieve gamma >= 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 gamma=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(m n(1/k)) time. For the same stretch, and assuming the query time is n(o(1)) Abboud et al. proved an Omega(m(1+1/12.7552 center dot k)) lower bound on the preprocessing time; we improve it to Omega(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-epsilon 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 (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-Szemeredi-Gowers theorem and Ruszas 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.