Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time

We present a new distance oracle in the fully dynamic setting: given a weighted undirected graph $G=(V,E)$ with $n$ vertices undergoing both edge insertions and deletions, and an arbitrary parameter $ε$ where $ε\in[1/\log^{c} n,1]$ and $c>0$ is a small constant, we can deterministically maintain a data structure with $n^ε$ worst-case update time that, given any pair of vertices $(u,v)$, returns a $2^{{\rm poly}(1/ε)}$-approximate distance between $u$ and $v$ in ${\rm poly}(1/ε)\log\log n$ query time. Our algorithm significantly advances the state-of-the-art in two aspects, both for fully dynamic algorithms and even decremental algorithms. First, no existing algorithm with worst-case update time guarantees a $o(n)$-approximation while also achieving an $n^{2-Ω(1)}$ update and $n^{o(1)}$ query time, while our algorithm offers a constant $O_ε(1)$-approximation with $n^ε$ update time and $O_ε(\log \log n)$ query time. Second, even if amortized update time is allowed, it is the first deterministic constant-approximation algorithm with $n^{1-Ω(1)}$ update and query time. The best result in this direction is the recent deterministic distance oracle by Chuzhoy and Zhang [STOC 2023] which achieves an approximation of $(\log\log n)^{2^{O(1/ε^{3})}}$ with amortized update time of $n^ε$ and query time of $2^{{\rm poly}(1/ε)}\log n\log\log n$. We obtain the result by dynamizing tools related to length-constrained expanders [Haeupler-Räcke-Ghaffari, STOC 2022; Haeupler-Hershkowitz-Tan, 2023; Haeupler-Huebotter-Ghaffari, 2022]. Our technique completely bypasses the 40-year-old Even-Shiloach tree, which has remained the most pervasive tool in the area but is inherently amortized.