Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Polynomial Lower Bound for Distributed Graph Coloring in a Weak LOCAL
  Model   We show an $\Omega\big(\Delta^{\frac{1}{3}-\frac{\eta}{3}}\big)$ lower bound
on the runtime of any deterministic distributed
$\mathcal{O}\big(\Delta^{1+\eta}\big)$-graph coloring algorithm in a weak
variant of the \LOCAL\ model.
  In particular, given a network graph \mbox{$G=(V,E)$}, in the weak \LOCAL\
model nodes communicate in synchronous rounds and they can use unbounded local
computation. We assume that the nodes have no identifiers, but that instead,
the computation starts with an initial valid vertex coloring. A node can
\textbf{broadcast} a \textbf{single} message of \textbf{unbounded} size to its
neighbors and receives the \textbf{set of messages} sent to it by its
neighbors. That is, if two neighbors of a node $v\in V$ send the same message
to $v$, $v$ will receive this message only a single time; without any further
knowledge, $v$ cannot know whether a received message was sent by only one or
more than one neighbor.
  Neighborhood graphs have been essential in the proof of lower bounds for
distributed coloring algorithms, e.g., \cite{linial92,Kuhn2006On}. Our proof
analyzes the recursive structure of the neighborhood graph of the respective
model to devise an $\Omega\big(\Delta^{\frac{1}{3}-\frac{\eta}{3}}\big)$ lower
bound on the runtime for any deterministic distributed
$\mathcal{O}\big(\Delta^{1+\eta}\big)$-graph coloring algorithm.
  Furthermore, we hope that the proof technique improves the understanding of
neighborhood graphs in general and that it will help towards finding a lower
(runtime) bound for distributed graph coloring in the standard \LOCAL\ model.
Our proof technique works for one-round algorithms in the standard \LOCAL\
model and provides a simpler and more intuitive proof for an existing
$\Omega(\Delta^2)$ lower bound.

0
The categories of this paper are: hep-ph
10
The categories of this paper are: q-bio
2
The categories of this paper are: math
21
The categories of this paper are: adap-org
23
The categories of this paper are: solv-int
25
The categories of this paper are: patt-sol
17
The categories of this paper are: q-fin
11
The categories of this paper are: hep-lat
14
The categories of this paper are: math-ph
24
The categories of this paper are: dg-ga
20
The categories of this paper are: acc-phys
12
The categories of this paper are: nucl-th
8
The categories of this paper are: hep-ex
16
The categories of this paper are: stat
36
The categories of this paper are: cmp-lg
27
The categories of this paper are: comp-gas