Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las
  Vegas, and $O(n^{1/2-\epsilon})$-Time   We present two algorithms for dynamically maintaining a spanning forest of a
graph undergoing edge insertions and deletions. Our algorithms guarantee {\em
worst-case update time} and work against an adaptive adversary, meaning that an
edge update can depend on previous outputs of the algorithms. We provide the
first polynomial improvement over the long-standing $O(\sqrt{n})$ bound of
[Frederickson STOC'83, Eppstein, Galil, Italiano and Nissenzweig FOCS'92] for
such type of algorithms. The previously best improvement was $O(\sqrt{n
(\log\log n)^2/\log n})$ [Kejlberg-Rasmussen, Kopelowitz, Pettie and Thorup
ESA'16]. We note however that these bounds were obtained by deterministic
algorithms while our algorithms are randomized.
  Our first algorithm is Monte Carlo and guarantees an $O(n^{0.4+o(1)})$
worst-case update time, where the $o(1)$ term hides the $O(\sqrt{\log\log
n/\log n})$ factor. Our second algorithm is Las Vegas and guarantees an
$O(n^{0.49306})$ worst-case update time with high probability. Algorithms with
better update time either needed to assume that the adversary is oblivious
(e.g. [Kapron, King and Mountjoy SODA'13]) or can only guarantee an amortized
update time. Our second result answers an open problem by Kapron et al. To the
best of our knowledge, our algorithms are among a few non-trivial randomized
dynamic algorithms that work against adaptive adversaries.

23
The categories of this paper are: solv-int
21
The categories of this paper are: adap-org
6
The categories of this paper are: astro-ph
18
The categories of this paper are: econ
33
The categories of this paper are: plasm-ph
8
The categories of this paper are: hep-ex
7
The categories of this paper are: hep-th
20
The categories of this paper are: acc-phys
12
The categories of this paper are: nucl-th
0
The categories of this paper are: hep-ph
28
The categories of this paper are: alg-geom
25
The categories of this paper are: patt-sol
13
The categories of this paper are: quant-ph
10
The categories of this paper are: q-bio
4
The categories of this paper are: cond-mat
11
The categories of this paper are: hep-lat