Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Fully Dynamic Matching: Beating 2-Approximation in $\Delta^\epsilon$
  Update Time   In fully dynamic graphs, we know how to maintain a 2-approximation of maximum
matching extremely fast, that is, in polylogarithmic update time or better. In
a sharp contrast and despite extensive studies, all known algorithms that
maintain a $2-\Omega(1)$ approximate matching are much slower. Understanding
this gap and, in particular, determining the best possible update time for
algorithms providing a better-than-2 approximate matching is a major open
question.
  In this paper, we show that for any constant $\epsilon > 0$, there is a
randomized algorithm that with high probability maintains a $2-\Omega(1)$
approximate maximum matching of a fully-dynamic general graph in worst-case
update time $O(\Delta^{\epsilon}+\text{polylog } n)$, where $\Delta$ is the
maximum degree.
  Previously, the fastest fully dynamic matching algorithm providing a
better-than-2 approximation had $O(m^{1/4})$ update-time [Bernstein and Stein,
SODA 2016]. A faster algorithm with update-time $O(n^\epsilon)$ was known, but
worked only for maintaining the size (and not the edges) of the matching in
bipartite graphs [Bhattacharya, Henzinger, and Nanongkai, STOC 2016].

5
The categories of this paper are: gr-qc
4
The categories of this paper are: cond-mat
19
The categories of this paper are: eess
33
The categories of this paper are: plasm-ph
34
The categories of this paper are: chem-ph
3
The categories of this paper are: physics
31
The categories of this paper are: ao-sci
13
The categories of this paper are: quant-ph
6
The categories of this paper are: astro-ph
0
The categories of this paper are: hep-ph
22
The categories of this paper are: chao-dyn
14
The categories of this paper are: math-ph
15
The categories of this paper are: nucl-ex
32
The categories of this paper are: atom-ph
37
The categories of this paper are: supr-con
2
The categories of this paper are: math