In the last weeks, we ( Michal Dory, Sebastian Forster,  Yasamin Nazari, and  Tijn de Vos) have been working on improving our manuscript “New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths”. The focus of this paper is to obtain decremental algorithms for the approximate all-pairs shortest path problem. In this updated version, we simplify some of the algorithms and proofs. Moreover, we remark that our approach also gives an efficient static distance oracle. In particular, our result matches known conditional lower bounds for sparse graphs. We include this result explicitly in the new version.

The updated manuscript is accessible on  arXiv.