BARC Talk by Karl Bringmann

Fine-Grained Complexity of Distance Oracles

Abstract:
The classic Thorup-Zwick distance oracles allow to query k-approximate graph distances with O(1) query time and m^{1+O(1/k)} preprocessing time. We present fine-grained lower bounds showing that this tradeoff of approximation ratio, query time, and preprocessing time is near-optimal.

Specifically, we show that any k-approximate distance oracle has preprocessing time m^{1+Omega(1/k)} or query time m^{Omega(1/k)}, unless both the 3SUM and APSP hypotheses are false.

 Joint work with Amir Abboud, Seri Khoury and Or Zamir.