Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with
  Applications   We give the first non-trivial fully dynamic probabilistic tree embedding
algorithm for weighted graphs undergoing edge insertions and deletions. We
obtain a trade-off between amortized update time and expected stretch against
an oblivious adversary. At the two extremes of this trade-off, we can maintain
a tree of expected stretch $ O (\log^4 n) $ with update time $ m^{1/2 + o(1)} $
or a tree of expected stretch $ n^{o(1)} $ with update time $ n^{o(1)} $ (for
edge weights polynomial in $ n $). A guarantee of the latter type has so far
only been known for maintaining tree embeddings with average (instead of
expected) stretch [Chechik/Zhang, SODA '20].
  Our main result has direct implications to fully dynamic approximate distance
oracles and fully dynamic buy-at-bulk network design. For dynamic distance
oracles, our result is the first to break the $ O (\sqrt{m}) $ update-time
barrier. For buy-at-bulk network design, a problem which also in the static
setting heavily relies on probabilistic tree embeddings, we give the first
non-trivial dynamic algorithm. As probabilistic tree embeddings are an
important tool in static approximation algorithms, further applications of our
result in dynamic approximation algorithms are conceivable.
  From a technical perspective, we obtain our main result by first designing a
decremental algorithm for probabilistic low-diameter decompositions via a
careful combination of Bartal's ball-growing approach [FOCS '96] with the
pruning framework of Chechik and Zhang [SODA '20]. We then extend this to a
fully dynamic algorithm by enriching a well-known 'decremental to fully
dynamic' reduction with a new bootstrapping idea to recursively employ a fully
dynamic algorithm instead of a static one in this reduction.

36
The categories of this paper are: cmp-lg
15
The categories of this paper are: nucl-ex
3
The categories of this paper are: physics
23
The categories of this paper are: solv-int
27
The categories of this paper are: comp-gas
24
The categories of this paper are: dg-ga
0
The categories of this paper are: hep-ph
7
The categories of this paper are: hep-th
28
The categories of this paper are: alg-geom
33
The categories of this paper are: plasm-ph
31
The categories of this paper are: ao-sci
16
The categories of this paper are: stat
4
The categories of this paper are: cond-mat
17
The categories of this paper are: q-fin
12
The categories of this paper are: nucl-th
6
The categories of this paper are: astro-ph