Our first corollary improves the \((3-\varepsilon )\)  hardness of Pătraşcu, Roditty, and Thorup [1]} all the way up to \(\omega (1)\) , showing that \(O(k)\) -approximation with \(O(m^{1+1/k})\)  preprocessing is indeed the right tradeoff for distance oracles with \(O(m^{1/k})\)  query time.
Our lower bound is comparable to that of Sommer, Verbin, and Yu [2]} in the cell-probe model, except that we allow much higher query time: \(m^{\Omega (1)}\)  vs. their \(O(1)\) .
Moreover, our lower bound applies to the easier offline version of the problem where all the queries are given in advance; previous lower bounds [3]}, [1]}, [2]} do not apply to this restricted setting.In the stronger models that these papers consider, where we measure space/probes rather than time, this offline problem becomes trivially easy.
If \(\omega =2\)  our lower bound becomes \(m^{1+\frac{1}{4k-2}-o(1)}\)  time for a \((k-\delta )\) -approximation; with the current \(\omega \)  it is \(\Omega (m^{1+\frac{1}{6.3776k-4.3777}})\) .
