Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


We give the first improvement to the space/approximation trade-off of distance oracles since the seminal result of Thorup and Zwick [STOC'01].

For unweighted graphs, our distance oracle has size O(n^{5/3}) = O(n^{1.66cdots}) and, when queried about vertices at distance d, returns a path of length 2d+1.

For weighted graphs with m=n^2/alpha edges, our distance oracle has size O(n^2 / sqrt[3]{alpha}) and returns a factor 2 approximation.

Based on a widely believed conjecture about the hardness of set intersection queries, we show that a 2-approximate distance oracle requires space Omega~(n^2 / sqrt{alpha}). For unweighted graphs, this implies an Omega~(n^{1.5}) space lower bound to achieve approximation 2d+1.

Questions and Answers

You need to be logged in to be able to post here.