Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Faster Deterministic Distributed Coloring Through Recursive List
  Coloring   We provide novel deterministic distributed vertex coloring algorithms. As our
main result, we give a deterministic distributed algorithm to compute a
$(\Delta+1)$-coloring of an $n$-node graph with maximum degree $\Delta$ in
$2^{O(\sqrt{\log\Delta})}\cdot\log n$ rounds. This improves on the best
previously known time complexity for a large range of values of $\Delta$. For
graphs with arboricity $a$, we obtain a deterministic distributed algorithm to
compute a $(2+o(1))a$-coloring in time $2^{O(\sqrt{\log a})}\cdot\log^2 n$.
Further, for graphs with bounded neighborhood independence, we show that a
$(\Delta+1)$-coloring can be computed more efficiently in time
$2^{O(\sqrt{\log\Delta})} + O(\log^* n)$. This in particular implies that also
a $(2\Delta-1)$-edge coloring can be computed deterministically in
$2^{O(\sqrt{\log\Delta})} + O(\log^* n)$ rounds, which improves the best known
time bound for small values of $\Delta$. All results even hold for the list
coloring variants of the problems. As a consequence, we also obtain an improved
deterministic $2^{O(\sqrt{\log\Delta})}\cdot\log^3 n$-round algorithm for
$\Delta$-coloring non-complete graphs with maximum degree $\Delta\geq 3$. Most
of our algorithms only require messages of $O(\log n)$ bits (including the
$(\Delta+1)$-vertex coloring algorithms).
  Our main technical contribution is a recursive deterministic distributed list
coloring algorithm to solve list coloring problems with lists of size
$\Delta^{1+o(1)}$. Given some list coloring problem and an orientation of the
edges, we show how to recursively divide the global color space into smaller
subspaces, assign one of the subspaces to each node of the graph, and compute a
new edge orientation such that for each node, the list size to out-degree ratio
degrades at most by a constant factor on each recursion level.

18
The categories of this paper are: econ
32
The categories of this paper are: atom-ph
5
The categories of this paper are: gr-qc
0
The categories of this paper are: hep-ph
16
The categories of this paper are: stat
23
The categories of this paper are: solv-int
25
The categories of this paper are: patt-sol
6
The categories of this paper are: astro-ph
7
The categories of this paper are: hep-th
9
The categories of this paper are: nlin
15
The categories of this paper are: nucl-ex
13
The categories of this paper are: quant-ph
36
The categories of this paper are: cmp-lg
11
The categories of this paper are: hep-lat
19
The categories of this paper are: eess
14
The categories of this paper are: math-ph