Title: A Time Hierarchy Theorem for the LOCAL Model,
Abstract: The celebrated Time Hierarchy Theorem for Turing machines states, informally,
that more problems can be solved given more time. The extent to which a time
hierarchy-type theorem holds in the distributed LOCAL model has been open for
many years. It is consistent with previous results that all natural problems in
the LOCAL model can be classified according to a small constant number of
complexities, such as $O(1),O(\log^* n), O(\log n), 2^{O(\sqrt{\log n})}$, etc.
In this paper we establish the first time hierarchy theorem for the LOCAL
model and prove that several gaps exist in the LOCAL time hierarchy.
1. We define an infinite set of simple coloring problems called Hierarchical
$2\frac{1}{2}$-Coloring}. A correctly colored graph can be confirmed by simply
checking the neighborhood of each vertex, so this problem fits into the class
of locally checkable labeling (LCL) problems. However, the complexity of the
$k$-level Hierarchical $2\frac{1}{2}$-Coloring problem is $\Theta(n^{1/k})$,
for $k\in\mathbb{Z}^+$. The upper and lower bounds hold for both general graphs
and trees, and for both randomized and deterministic algorithms.
2. Consider any LCL problem on bounded degree trees. We prove an
automatic-speedup theorem that states that any randomized $n^{o(1)}$-time
algorithm solving the LCL can be transformed into a deterministic $O(\log
n)$-time algorithm. Together with a previous result, this establishes that on
trees, there are no natural deterministic complexities in the ranges
$\omega(\log^* n)$---$o(\log n)$ or $\omega(\log n)$---$n^{o(1)}$.
3. We expose a gap in the randomized time hierarchy on general graphs. Any
randomized algorithm that solves an LCL problem in sublogarithmic time can be
sped up to run in $O(T_{LLL})$ time, which is the complexity of the distributed
Lovasz local lemma problem, currently known to be $\Omega(\log\log n)$ and
$O(\log n)$.