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 n1/2-regular graph is n2−o(1)-hard even when the number of short cycles is small; namely, when the number of k-cycles is O(nk/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.