arXiv:1704.06297v1 [cs.DC] 20 Apr 2017

A Time Hierarchy Theorem for the LOCAL Model∗
Yi-Jun Chang
University of Michigan

Seth Pettie
University of Michigan

cyijun@umich.edu

pettie@umich.edu

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 classic
distributed LOCAL model has been open for many years. In particular, 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 Op1q, Oplog˚ nq, Oplog nq, 2Op log nq , 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. Our main results are as follows:
• We define an infinite set of simple coloring problems called Hierarchical 2 12 -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 klevel Hierarchical 2 21 -Coloring problem is Θpn1{k q, for k P Z` . The upper and lower bounds hold
for both general graphs and trees, and for both randomized and deterministic algorithms.
• Consider any LCL problem on bounded degree trees. We prove an automatic-speedup theorem
that states that any randomized nop1q -time algorithm solving the LCL can be transformed into a
deterministic Oplog nq-time algorithm. Together with a previous result [6], this establishes that on
trees, there are no natural deterministic complexities in the ranges ωplog˚ nq—oplog nq or ωplog nq—
nop1q .
• We expose a gap in the randomized time hierarchy on general graphs. Roughly speaking, any
randomized algorithm that solves an LCL problem in sublogarithmic time can be sped up to run in
OpTLLL q time, which is the complexity of the distributed Lovász local lemma problem, currently
known to be Ωplog log nq and Oplog nq.
Finally, we revisit Naor and Stockmeyer’s characterization of Op1q-time LOCAL algorithms for LCL
problems (as order-invariant w.r.t. vertex IDs) and calculate the complexity gaps
are directly implied
? that?
byatheir proof. For n-rings we see a ωp1q—oplog˚ nq complexity gap, for p n ˆ nq-tori an ωp1q—
op log˚ nq gap, and for bounded degree trees and general graphs, an ωp1q—oplogplog˚ nqq complexity
gap.

∗ Supported

by NSF Grants CCF-1514383 and CCF-1637546.

1

Introduction

The goal of this paper is to understand the spectrum of natural problem complexities that can exist in the
LOCAL model [31, 37] of distributed computation, and to quantify the value of randomness in this model.
Whereas the time hierarchy of Turing machines is known1 to be very “smooth”, recent work [6, 5] has
exhibited strange gaps in the LOCAL complexity hierarchy. Indeed, prior to this work it was not even known
if the LOCAL model could support more than a small constant number of problem complexities. Before
surveying prior work in this area, let us formally define the deterministic and randomized variants of the
LOCAL model, and the class of locally checkable labeling (LCL) problems, which are intuitively those graph
problems that can be computed locally in nondeterministic constant time.
In both the DetLOCAL and RandLOCAL models the input graph G “ pV, Eq and communications network
are identical. Each vertex hosts a processor and all vertices run the same algorithm. Each edge supports
communication in both directions. The computation proceeds in synchronized rounds. In a round, each processor performs some computation and sends a message along each incident edge, which is delivered before
the beginning of the next round. Each vertex v is initially aware of its degree degpvq, a port numbering mapdef
def
ping its incident edges to t1, . . . , degpvqu, certain global parameters such as n “ |V |, ∆ “ maxvPV degpvq,
and possibly other information. The assumption that global parameters are common knowledge can sometimes be removed; see Korman, Sereni, and Viennot [28]. The only measure of efficiency is the number of
rounds. All local computation is free and the size of messages is unbounded. Henceforth “time” refers to
the number of rounds. The differences between DetLOCAL and RandLOCAL are as follows.
DetLOCAL: In order to avoid trivial impossibilities, all vertices are assumed to hold unique Θplog nq-bit
IDs. Except for the information about degpvq, IDpvq, and the port numbering, the initial state of v is
identical to every other vertex. The algorithm executed at each vertex is deterministic.
RandLOCAL: In this model each vertex may locally generate an unbounded number of independent truly
random bits. (There are no globally shared random bits.) Except for the information about degpvq
and its port numbering, the initial state of v is identical to every other vertex. Algorithms in this
model operate for a specified number of rounds and have some probability of failure, the definition of
which is problem specific. We set the maximum tolerable global probability of failure to be 1{n.
Clearly RandLOCAL algorithms can generate distinct IDs (w.h.p.) if desired. Observe that the role of
“n” is different in the two LOCAL models: in DetLOCAL it affects the ID length whereas in RandLOCAL it
affects the failure probability.
LCL Problems. Naor and Stockmeyer [35] introduced locally checkable labelings to formalize a large class
of natural graph problems. Fix a class G of possible input graphs and let ∆ be the maximum degree in any
such graph. Formally, an LCL problem P for G has a radius r, constant size input and output alphabets
Σin , Σout , and a set C of acceptable configurations. All of these parameters may depend on ∆. Each C P C
is a graph centered at a specific vertex, in which each vertex has a degree, a port numbering, and two labels
from Σin and Σout . Given the input graph GpV, E, φin q where φin : V pGq Ñ Σin , an acceptable output is
any function φout : V pGq Ñ Σout such that for each v P V pGq, the subgraph induced by N r pvq (denoting the
r-neighborhood of v together with information stored there: vertex degrees, port numberings, input labels,
and output labels) is isomorphic to a member of C. An LCL can be described explicitly by enumerating
a finite number of acceptable configurations. LCLs can be generalized to graph classes with unbounded
degrees.
Many natural symmetry breaking problems can be expressed as LCLs, such as MIS, maximal matching,
pα, βq-ruling sets, p∆ ` 1q-vertex coloring, and sinkless orientation.

1.1

The Complexity Landscape of LOCAL

The complexity landscape for LCL problems is defined by “natural” complexities (sharp lower and upper
bounds for specific LCL problems) and provably empty gaps in the complexity spectrum. We now have
1 For

any time-constructible function T pnq, there is a problem solvable in OpT pnqq but not opT pnqq time [23, 12].

1

an almost perfect
of the complexity landscape for two simple topologies: n-rings [8, 31,
?
? understanding
34, 35, 6] and p n ˆ nq-tori [35, 6, 5]. See Figure 1, Top and Middle. On the n-ring, the only possible
problem complexities are Op1q, Θplog˚ nq (e.g., 3-coloring), and Θpnq (e.g., 2-coloring, if bipartite). The gaps
between these three complexities are obtained by automatic speedup theorems. Naor and Stockmeyer’s [35]
characterization of Op1q-time LCL algorithms actually implies that any oplog˚ nq-time algorithm on the nring can be transformed to run in Op1q time; see Appendix A. Chang, Kopelowitz, and Pettie [6] showed
˚
that any opnq-time RandLOCAL
?algorithm can be made to run in Oplog nq time in DetLOCAL.
?
is almost identical [5]: every known LCL has complexity Op1q,
The situation with p n ˆ nq-tori
?
nq
(e.g.,
3-coloring). Whereas the gap implied by [35] is ωp1q—oplog˚ nq
Θplog˚ nq (e.g., 4-coloring), or
Θp
a ˚
?
?
on the n-ring, it is ωp1q—op log nq on the p n ˆ nq-torus; see Appendix A.2 Whereas randomness is
known not to help in n-rings [35, 6], it is an open question on tori [5]. Whereas the classification question
is?decidable
on n-rings (whether an LCL is Oplog˚ nq or Ωpnq, for example) this question is undecidable on
?
p n ˆ nq-tori [35, 5].
The gap theorems of Chang et al. [6] show that no LCL problem on general graphs has DetLOCAL complexity in the range ωplog˚ nq—oplog∆ nq, nor RandLOCAL complexity in the range ωplog˚ nq—oplog∆ log nq.
Some problems exhibit an exponential separation (Oplog∆ log nq vs. Ωplog∆ nq) between their RandLOCAL
and DetLOCAL complexities, such as ∆-coloring degree-∆ trees [4, 6] and sinkless orientation [4, 15]. More
generally, Chang et al. [6] proved that the RandLOCAL complexity of any ?
LCL problem on graphs of size n is,
holding ∆ fixed, at least its deterministic complexity on instances of size log n. Thus, on the class of degree
∆ “ Op1q graphs there were only five known natural complexities: Op1q, Θplog˚ nq, randomized Θplog log nq,
Θplog nq, and Θpnq. For non-constant
b ∆, the RandLOCAL lower bounds of Kuhn, Moscibroda, and Wattenhofer [29] imply Ωpmint logloglog∆∆ , logloglogn n uq lower bounds on Op1q-approximate vertex cover, MIS, and
maximal matching. This Ωplog ∆{ log log ∆q lower bound is only known to be tight for Op1q-approximate
vertex
b cover [2]; the best maximal matching [3] and MIS [13] algorithms’ dependence on ∆ is Ωplog ∆q. The

Ωp logloglogn n q lower bound is not known to be tight for any problem, but is almost tight for maximal matching
on bounded arboricity graphs [3], e.g., trees or planar graphs.
New Results. In this paper we study the LOCAL complexity landscape on more general topologies:
bounded degree trees and general graphs; see Figure 1, Bottom. We establish a new complexity gap for
trees, a potential complexity gap for general graphs (which depends on the distributed complexity of the
constructive Lovász local lemma), and a new infinite hierarchy of coloring problems with polynomial time
complexities. In more detail,
• We prove that on the class of degree bounded trees, no LCL has complexity in the range ωplog nq—nop1q .
Specifically, any nop1q -time RandLOCAL algorithm can be converted to an Oplog nq-time DetLOCAL
algorithm. Moreover, given a description of an LCL problem P, it is decidable whether the RandLOCAL
complexity of P is nΩp1q or the DetLOCAL complexity of P is Oplog nq.
It turns out that this gap is maximal: we cannot extend it lower than ωplog nq [31, 6], nor higher than
nop1q , as we show below.
• We define an infinite class of LCL problems called Hierarchical 2 21 -Coloring. We prove that k-level
Hierarchical 2 21 -Coloring has complexity Θpn1{k q. The upper bound holds in DetLOCAL on general
graphs, and the lower bound holds even on degree-3 trees in RandLOCAL. Thus, in contrast to rings
and tori, trees and general graphs support an infinite number of natural problem complexities.
• Suppose we have a RandLOCAL algorithm for general graphs running in Cp∆q`oplog∆ nq time. We can
transform this algorithm to run in OpCp∆q ¨ TLLL q time, where TLLL is the complexity of a weak (i.e.,
“easy”) version of the constructive Lovász local lemma. At present, TLLL is known to be Ωplog log nq
and Oplog nq on bounded degree graphs. If it turns out that TLLL is sublogarithmic, this establishes a
new RandLOCAL complexity gap between ωpTLLL q and oplog nq on bounded degree graphs.

2 J. Suomela (personal communication, 2017) has a proof that there is an ωp1q—oplog˚ nq complexity gap for tori, at least
for LCLs that do not use port numberings or input labels. The issues that arise with port numbering and input labels can be
very subtle.

2

Figure 1: Top: the complexity landscape
for LCL problems on the n-ring. Middle: the complexity
?
?
landscape for LCL problems on the p n ˆ nq-torus. Refer to [35, 6, 5] and Appendix A for proofs of
the complexity gaps (‘X’) on rings and tori. Bottom: the complexity landscape for LCL problems on
bounded degree trees. The ωplog˚ nq—oplog nq DetLOCAL gap and ωplog˚ nq—oplog log nq RandLOCAL gap
are due to [6]. The ωpLLLq—oplog nq and ωplog nq—nop1q gaps are new. Refer to Appendix A for the ωp1q—
oplogplog˚ nqq gap. It is unknown whether there are ωpn1{pk`1q q—opn1{k q gaps. With the exception of the
ωplog nq—nop1q gap, this is exactly the known complexity landscape for general bounded degree graphs as
well.
Finally, it seems to be folklore that Naor and Stockmeyer’s work [35] implies some kind of complexity gap,
which has been cited as ωp1q—oplog˚ nq [5, p. 2]. However, to our knowledge, no proof of this complexity gap
has been published. We show how Naor and Stockmeyer’s approach implies complexity gaps that depend
on the graph topology:
— ωp1q—oplog˚ nq on rings.
a
— ωp1q—op log˚ nq on tori.
— ωp1q—oplogplog˚ nqq on bounded degree trees and general graphs.
These gaps apply to the general class of LCL problems defined in this paper, in which vertices initially
hold an input label and possible port numbering. Port numberings are needed to represent “edge labeling”
problems (like maximal matching, edge coloring, and sinkless orientation) unambiguously as vertex labelings.
They are not needed for native “vertex labeling” problems like p∆ ` 1q-coloring or MIS. J. Suomela (personal
communication) gave a proof that the ωp1q—oplog˚ nq gap exists in tori as well, for the class of LCL problems
without input labels or port numbering; see Appendix A.
Commentary. Our ωplog nq—nop1q complexity gap for trees is interesting from both a technical and greater
philosophical perspective, due to the fact that many natural problems have been “stuck” at nop1q complexities
?
for decades. Any DetLOCAL algorithm that relies on network decompositions [36] currently takes 2Op log nq
time. If our automatic speedup theorem could be extended to the class of all graphs, this would immediately
yield Oplog nq-time algorithms for MIS, p∆ ` 1q-coloring, and many other LCLs.
All the existing automatic speedup theorems are quite different in terms of proof techniques. Naor and
Stockmeyer’s approach is based on Ramsey theory. The speedup theorems
oplog∆ nq
? of [6, 5] use the fact?that ?
algorithms on general graphs (and opnq algorithms on n-rings and op nq algorithms on p n ˆ nq-tori)
cannot “see” the whole graph, and can therefore be efficiently tricked into thinking the graph has constant
size. Our nop1q Ñ Oplog nq speedup theorem introduces an entirely new set of techniques based on classic
3

automata theory. We show that any LCL problem gives rise to a regular language that represents partial
labelings of the tree that can be consistently extended to total lablelings. By applying the pumping lemma for
regular languages, we can “pump” the input tree into a much larger tree that behaves similar to the original
tree. The advantage of creating a larger imaginary tree is that each vertex can (mentally) simulate the
behavior of an nop1q -time algorithm on the imaginary tree, merely by inspecting its Oplog nq-neighborhood
in the actual tree. Moreover, because the pumping operation preserves properties of the original tree, a
labeling of the imaginary tree can be efficiently converted to a labeling of the original tree.

1.2

Related Results

There are several LOCAL lower bounds for natural problems that do not quite fit in the LCL framework.
Göös, Hirvonen, and Suomela [16] proved a sharp Ωp∆q lower bound for fractional maximal matching and
Göös and Suomela proved Ωplog nq lower bounds on p1 ` δq-approximating the minimum vertex cover, δ ą 0,
even on degree-3 graphs. See [30, 25] for lower bounds on coloring problems that apply to constrained
algorithms or a constrained version of the LOCAL model.
In recent years there have been efforts to develop a ‘complexity theory’ of locality. The gap theorems
of [35, 6, 5] have already been discussed. Suomela surveys [38] the class of problems that can be computed
with Op1q time. Fraigniaud et al. [11] defined a distributed model for locally deciding graph properties;
see [9] for a survey of variants of the local distributed decision model. Göös and Suomela [17] considered
the proof complexity (measured in terms of bits-per-vertex label) of locally verifying graph properties. Very
recently, Ghaffari, Kuhn, and Maus [14] defined the SLOCAL model (sequential LOCAL) and exhibited several
complete problems for this model, inasmuch as a polylogpnq-time DetLOCAL algorithm for any complete
problem implies a polylogpnq DetLOCAL algorithm for every polylogpnq-time problem in SLOCAL.3

1.3

Organization

In Section 2 we introduce Hierarchical 2 21 -Coloring and prove that the k-level variant of this problem has
complexity Θpn1{k q. In Section 3 we prove the nop1q Ñ Oplog nq speedup theorem for bounded degree trees.
In Section 4 we discuss the constructive Lovász local lemma and prove the oplog∆ nq Ñ TLLL randomized
speedup theorem. In Section 5 we discuss open problems and outstanding conjectures. Appendix A reviews
Naor and Stockmeyer’s characterization of Op1q-time LCL algorithms, using Ramsey theory, and explains
how it implies gaps in the complexity hierarchy that depend on graph topology.

2

An Infinitude of Complexities: Hierarchical 2 12 -Coloring

In this section we give an infinite sequence pPk qkPZ` of LCL problems, where the complexity of Pk is precisely
Θpn1{k q.4 The upper bound holds on general graphs in DetLOCAL and the lower bound holds in RandLOCAL,
even on degree-3 trees. Informally, the task of Pk is to 2-color (with tB, Du) certain specific subgraphs of
the input graph. Some vertices are exempt from being colored (in which case they are labeled F), and in
addition, it is possible to decline to 2-color certain subgraphs, by labeling them A.
There are no input labels. The output label set is Σout “ tB, D, A, Fu.5 The problem Pk is an LCL defined
by the following rules.
Levels. Subsequent rules depend on the levels of vertices. Let Vi , i P t1, . . . , k ` 1u, be the set of vertices
3 The

class of Op1q-time SLOCAL algorithms is, roughly speaking, those graph labelings that can be computed sequentially,
by a truly local algorithm. This class is a strict subset of LCLs.
4 Brandt et al. [5, Appendix A.3] described an LCL that has complexity Θp?nq on general graphs, but not trees. It may be
possible to generalize their LCL to any complexity of the form Θpn1{k q.
5 Venus, Mars, Mercury, Saturn.

4

on level i, defined as follows.
G1 “ G
Gi “ Gi´1 ´ Vi´1 ,

for i P r2, k ` 1s

Vi “ tv P V pGi q | degGi pvq ď 2u,

for i P r1, ks

Vk`1 “ V pGk`1 q

(the remaining vertices)

Remember that vertices know their degrees, so a vertex in V1 deduces this with 0 rounds of communication. In general the level of v can be calculated from information in N k pvq.
Exemption. A vertex labeled F is called exempt. No V1 vertex is labeled F; all Vk`1 vertices are labeled F.
Any Vi vertex is labeled F iff it is adjacent to a lower level vertex labeled B, D, or F. Define Di Ď Vi
to be the set of level i exempt vertices.
Two-Coloring. Vertices not covered by the exemption rule are labeled one of B, D, A.
— Any vertex in Vi , i P r1, ks, labeled B has no neighbor in Vi labeled B or A.
— Any vertex in Vi , i P r1, ks, labeled D has no neighbor in Vi labeled D or A.
— Any vertex in Vk ´ Dk with exactly 0 or 1 neighbors in Vk ´ Dk must be labeled B or D.
Commentary. The Level rule states that the graph induced by Vi consists of paths and cycles. The TwoColoring rule implies that each component of non-exempt vertices in the graph induced by Vi ´ Di must
either (a) be labeled uniformly by A or (b) be properly 2-colored by tB, Du. Every path in Vk ´ Dk must be
properly 2-colored, but cycles in Vk ´ Dk are allowed to be labeled uniformly by A. This last provision is
necessary to ensure that every graph can be labeled according to Pk since there is no guarantee that cycles
in Vk ´ Dk are bipartite.
Remark 1. As stated Pk is an LCL with an alphabet size of 4 and a radius k, since the coloring rules refer
to levels, which can be deduced by looking up to radius k. On the other hand, we can also represent Pk as
an LCL with radius 1 and alphabet size 4k by including a vertex’s level in its output label. A correct level
assignment can be verified within radius 1. For example, level 1 vertices are those with degree at most 2, and
a vertex is labeled i P r2, ks iff all but at most 2 neighbors have levels less than i.
Theorem 1. The DetLOCAL complexity of Pk on general graphs is Opn1{k q.
Proof. The algorithm fixes the labeling of V1 , . . . , Vk , Vk`1 in order, according to the following steps. Assume
that all vertices in V1 , . . . , Vi´1 have already been labeled.
• Compute Di according to the Exemption rule. (E.g., D1 “ H, Dk`1 “ Vk`1 .)
P
T
• Each path in the subgraph induced by Vi ´ Di calculates its length. If it contains at most 2n1{k
vertices, it properly 2-colors itself with tB, Du; longer paths and cycles in Vi ´ Di label themselves
uniformly by A.
This algorithm correctly solves Pk provided that it never labels a path in Vk ´ Dk with A. Let Ui be
the subgraph induced by those vertices in V1 Y ¨ ¨ ¨ Y Vi labeled A. Consider a connected component C in
Ui whose Vi -vertices are arranged in a path (not a cycle). We argue by induction that C has at least 2ni{k
vertices. This
true in the base case i “ 1: if a path component of U1 were colored A, it must have
P is clearly
T
more than 2n1{k vertices. Now assume the claim is true for i ´ 1 and consider a component C of Ui . If
the Vi -vertices in C form a path, it must have length greater than 2n1{k . Each vertex in that path must
be adjacentP to anT endpoint of a Vi´1 path. Since Vi´1 paths have two endpoints, the Vi path is adjacent
to at least 2n1{k {2 ě n1{k components in Ui´1 , each of which has size at least 2npi´1q{k , by the inductive
hypothesis. Thus, the size of C is at least n1{k ¨ 2npi´1q{k ` 2n1{k ą 2ni{k . Because there are at most n
vertices in the graph, it is impossible for Vk vertices arranged in a path to be colored A.
Theorem 2. The RandLOCAL complexity of Pk on trees with maximum degree ∆ “ 3 is Ωpn1{k q.
5

Figure 2: The graph Hk with parameters k “ 3, x “ 7. White vertices are in V1 , gray in V2 , and black in
V3 . V4 “ Vk`1 is empty.
Proof. Fix an integer parameter x and define a sequence of graphs pHi q1ďiďk as follows. Each Hi has a head
and a tail.
• H1 is a path (or backbone) of length x. One end of the path is the head and the other end the tail.
• To construct Hi , i P r2, k ´ 1s, begin with a backbone path pv1 , v2 , . . . , vx q, with head v1 and tail vx .
pjq
pjq
Form x ` 1 copies pHi´1 q1ďjďx`1 of Hi´1 , where v pjq is the head of Hi´1 . Connect v pjq to vj by an
edge, for j P r1, xs, and also connect v px`1q to vx by an edge.
• Hk is constructed exactly as above, except that we generate x ` 2 copies of Hk´1 and connect the
heads of two copies of Hk´1 to both v1 and vx . See Figure 2 for an example with k “ 3.
Let us make several observations about the construction of Hk . First, it is a tree with maximum degree
3. Second, when decomposing V pHk q into levels pV1 , . . . , Vk , Vk`1 q, Vi is precisely the union of the backbones
in all copies of Hi , and Vk`1 “ H. Third, the number of vertices in Hk is Θpxk q, so a opn1{k q algorithm for
Pk must run in opxq time on Hk .
Consider a RandLOCAL algorithm A solving Pk on Hk within t ă x{5 ´ Op1q time, that fails with
probability pfail . If A is a good algorithm then pfail ď 1{|V pHk q|. However, we will now show that pfail is
constant, independent of |V pHk q|.
Define Ei to be the event that Di ‰ H and pi “ PrpEi q. By an induction from i “ 2 to k, we prove that
pi ď 2pi ´ 1q ¨ pfail .
Base case.

We first prove that
Pr pHk is not correctly colored according to Pk | E2 q ě 1{2.

Conditioning on E2 means that D2 ‰ H. Fix any v P D2 and let P be a copy of H1 (a path) adjacent to v.
In order for v P D2 , it must be that P is properly 2-colored with tB, Du. Since t ă x{5 ´ Op1q, there exist
two vertices u and u1 in P such that
1. N t puq, N t pu1 q, and N t pvq are disjoint sets,
2. the subgraphs induced by N t puq and N t pu1 q are isomorphic, and
3. the distance between u and u1 is odd.
Let pB and pD be the probabilities that u/u1 is labeled B and D, respectively. A proper 2-coloring of P
assigns u and u1 different colors, and that occurs with probability 2pB pD ď 2pB p1 ´ pB q ď 1{2. Moreover,
this holds independent of the random bits generated by vertices in N t pvq. The algorithm fails unless u, u1
have different colors, thus pfail ě p2 {2, and hence p2 ď 2 ¨ pfail .

6

Inductive Step. Let 3 ď i ď k. The inductive hypothesis states that pi´1 ď 2pi ´ 2q ¨ pfail . By a proof
similar to the base case, we have that:
Pr pHk is not correctly colored according to Pk | Ei zEi´1 q ě 1{2.
We are conditioning on Ei zEi´1 . If this event is empty, then pi ď pi´1 ď 2pi ´ 2q ¨ pfail and the induction is
complete. On the other hand, if Ei zEi´1 holds then there is some v P Di adjacent to a copy of Hi´1 with
backbone path P , where P X Di´1 “ H. In other words, if Hk is colored according to Pk then P must be
properly 2-colored with tB, Du. The argument above shows this occurs with probability at least 1/2. Thus,
pfail “ PrpHk is incorrectly coloredq ě PrpEi zEi´1 q{2 ě ppi ´ pi´1 q{2,
or pi ď 2pfail ` pi´1 ď 2pi ´ 1qpfail , completing the induction.
Finally, let P be the path induced by vertices in Vk . The probability that Ek holds (P X Dk ‰ H) is
pk ď 2pk ´ 1q ¨ pfail . On the other hand, PrpHk not colored correctly | Ek q ě 1{2 by the argument above,
hence pfail ě p1 ´ pk q{2, or pk ě 1 ´ 2pfail . Combining the upper and lower bounds on pk we conclude
that pfail ě p2kq´1 is constant, independent of |V pHk q|. Thus, algorithm A cannot succeed with high
probability.

3

A Complexity Gap on Bounded Degree Trees

In this section we prove an nop1q Ñ Oplog nq speedup theorem for LCL problems on bounded degree trees.
The progression of definitions and lemmas in Sections 3.2–3.13 is logical, but obscures the high level structure
of the proof. Section 3.1 gives an informal tour of the proof and its key ideas. Throughout, P is a radius-r
LCL and A is an nop1q -time algorithm for P on bounded degree trees.

3.1

A Tour of the Proof

Consider this simple way to decompose a tree in Oplog nq time, inspired by Miller and Reif [32]. Iteratively
remove paths of degree-2 vertices (compress) and vertices with degree 0 or 1 (rake). Vertices removed in
iteration i are at level i. If Oplog nq rakes alone suffice to decompose a tree then it has Oplog nq diameter
and any LCL can be solved in Oplog nq time on such a graph. Thus, we mainly have to worry about the
situation where compress removes very long (ωp1q-length) paths.
The first observation is that it is easy to split up long degree-2 paths of level-i vertices into constant
length paths, by artificially promoting a well-spaced subset of level-i vertices to level i ` 1. Thus, we have
a situation that looks like this: level-i vertices are arranged in an Op1q-length path, each the root of a
(colored) subtree of level-pă iq vertices that were removed in previous rake/compress steps, and bookended
by level-pą iq (black) vertices. Call the subgraph between the bookends H.

In our approach it is the level-pą iq vertices that are in charge of coordinating the labeling of level-pď iq
vertices in their purview. In this diagram, H is in the purview of both black bookends. We only have one
tool available for computing a labeling of this subgraph: an nop1q -time RandLOCAL algorithm A that works
w.h.p. What would happen if we simulated A on H? The simulation would fail catastrophically of course,
since it needs to look up to an nop1q radius, to parts of the graph far outside of H.
Note that the colored subtrees are unbounded in terms of size and depth. Nonetheless, they fall into
a constant number of equivalence classes in the following sense. The class of a rooted tree is the set of
7

all labelings of the r-neighborhood of its root that can be extended to total labelings of the tree that are
consistent with P.

In other words, the large and complex graph H can be succinctly encoded as a simple class vector
pc1 , c2 , . . . , c` q, where cj is the class of the jth colored tree. Consider the set of all labelings of H that are
consistent with P. This set can also be succinctly represented by listing the labelings of the r-neighborhoods
of the bookends that can be extended to all of H, while respecting P. The set of these partial labelings
defines the type of H. We show that H’s type can be computed by a finite automaton that reads the class
vector pc1 , . . . , c` q one character at a time. By the pigeonhole principle, if ` is sufficiently large then the
automaton loops, meaning that pc1 , . . . , c` q can be written as x ˝ y ˝ z, which has the same type as every
x ˝ y j ˝ z, for all j ě 1. This pumping lemma for trees lets us dramatically expand the size of H without
affecting its type, i.e., how it interacts with the outside world beyond the bookends.

This diagram illustrates the pumping lemma with a substring of |y| “ 3 trees (rooted at gray vertices)
repeated j “ 3 times. Now let us reconsider the simulation of A. If we first pump H to be long enough, and
then simulate A on the middle section of pumped-H, A must, according to its nop1q time bound, compute a
labeling without needing any information outside of pumped-H, i.e., beyond the bookends. Thus, we can use
A to pre-commit to a labeling of a small (radius-r) subgraph of pumped-H. Given this pre-commitment,
the left and right bookends no longer need to coordinate their activities: everything left (right) of the precommitted zone is now in the purview of the left (right) bookend. Interestingly, these manipulations (tree
surgery and pre-commitments) can be repeated for each i, yielding a hierarchy of imaginary trees such that
a proper labeling at one level of the hierarchy implies a proper labeling at the previous level.
Roadmap. This short proof sketch has been simplified to the point that it is riddled with small inaccuracies. Nonetheless, it does accurately capture the difficulties, ideas, and techniques used in the actual
proof. In Section 3.2 we formally define the notion of a partially labeled graph, i.e., one with certain vertices
pre-commited to their output labels. Section 3.3 defines a surgical “cut-and-paste” operation on graphs. Section 3.4 defines a partition of the vertices of a subgraph H, which differentiates between vertices that “see”
the outside graph, and those that see only H. Section 3.5 defines an equivalence relation on graphs that,
intuitively, justifies surgically replacing a subgraph with an equivalent graph. Sections 3.6 and 3.7 explore
properties of the equivalence relation. Section 3.8 introduces the pumping lemma for trees, and Section 3.9
defines a specialized Rake/Compress-style graph decomposition. Section 3.10 presents the operations Extend
(which pumps a subtree) and Label (which pre-commits a small partial labeling) in terms of a black-box
labeling function f . Section 3.11 defines the set of all (partially labeled) trees that can be encountered, by
considering the interplay between the graph decomposition, Extend, and Label. It is important that for each
tree encountered, its partial labeling can be extended to a complete labeling consistent with P; whether this
actually holds depends on the choice of black-box f . Section 3.13 shows how a feasible labeling function f
can be extracted from any nop1q -time algorithm A and Section 3.12 shows that P can be solved in Oplog nq
8

time, given a feasible labeling function.

3.2

Partial Labeled Graphs

A partially labeled graph G “ pG, Lq is a graph G together with a function L : V pGq Ñ Σout Y tKu. The
vertices in L´1 pKq are unlabeled. A complete labeling L1 : V pGq Ñ Σout for G is one that labels all vertices
and is consistent with G’s partial labeling, i.e., L1 pvq “ Lpvq whenever Lpvq ‰ K. A legal labeling is a
complete labeling that is locally consistent for all v P V pGq, i.e., the labeled subgraph induced by N r pvq is
consistent with the LCL P. Here N r pvq is the set of all vertices within distance r of v.
All graph operations can be extended naturally to partially labeled graphs. For instance, a subgraph of
a partially labeled graph G “ pG, Lq is a pair H “ pH, L1 q such that H is a subgraph of G, and L1 is L
restricted to the domain V pHq. With slight abuse of notation, we usually write H “ pH, Lq.

3.3

Graph Surgery

Let G “ pG, Lq be a partially labeled graph, and let H “ pH, Lq be a subgraph of G. The poles of H are
those vertices in V pHq that are adjacent to some vertex in the outside graph V pGq ´ V pHq. We define an
operation Replace that surgically removes H and replaces it with some H1 .
Replace Let S “ pv1 , . . . , vp q be a list of the poles of H and let S “ pv11 , . . . , vp1 q be a designated set of
poles in some partially labeled graph H1 . The partially labeled graph G 1 “ ReplacepG, pH, Sq, pH1 , S 1 qq
is constructed as follows. Beginning with G, replace H with H1 , and replace any edge tu, vi u, u P
V pGq ´ V pHq, with tu, vi1 u. If the poles S, S 1 are clear from context, we may also simply write
G 1 “ ReplacepG, H, H1 q. Writing G 1 “ pG1 , L1 q and H1 “ pH 1 , L1 q, there is a natural 1-1 correspondence
between the vertices in V pGq ´ V pHq and V pG1 q ´ V pH 1 q.
In the proof of our nop1q Ñ Oplog nq speedup thereom we only consider unipolar and bipolar graphs
(p P t1, 2u) but for maximum generality we define everything w.r.t. graphs having p ě 1 poles.

Given a legal labeling L˛ of G, we would like to know whether there is a legal labeling L1˛ of G 1 that
agrees with L˛ , i.e., L˛ pvq “ L1˛ pv 1 q for each v P V pGq ´ V pHq and the corresponding v 1 P V pG1 q ´ V pH 1 q.
‹
Our goal is to define an equivalence relation „ on partially labeled graphs (with designated poles) so that
‹
1
1
the following is true: if pH, Sq „ pH , S q, then such a legal labeling L1˛ must exist, regardless of the choice
of G and L˛ . Observe that since P has radius r, the interface between V pHq (or V pH 1 q) and the rest of the
graph only occurs around the Oprq-neighborhoods of the poles of H (or H1 ). This motivates us to define a
certain partition of H’s vertices that depends on its poles and r.

3.4

A Tripartition of the Vertices

Let H “ pH, Lq be a partially labeledŤgraph with poles S “Ťpv1 , . . . , vp q. Define ξpH, Sq “ pD1 , D2 , D3 q to be
a tripartition of V pHq, where D1 “ vPS N r´1 pvq, D2 “ vPD1 N r pvq ´ D1 , and D3 “ V pHq ´ pD1 Y D2 q.
See Figure 3 for an illustration.
Consider the partition ξpH, Sq “ pD1 , D2 , D3 q of a partially labeled graph H “ pH, Lq. Let L˚ :
D1 Y D2 Ñ Σout assign output labels to D1 Y D2 . We say that L˚ is extendible (to all of V pHq) if there

9

Figure 3: A partially labeled subgraph H with poles S “ ps, tq, embedded in a larger graph G. In the
partition ξpH, Sq “ pD1 , D2 , D3 q, D1 is the set of vertices in V pHq within radius r ´ 1 of S, D2 are those
within radius 2r ´ 1 of S, excluding D1 , and D3 is the rest of V pHq. When H is embedded in some larger
graph G, D0 denotes the remaining vertices in V pGq ´ V pHq.
exists a complete labeling L˛ of H such that L˛ agrees with L where it is defined, agrees with L˚ on D1 YD2 ,
and is locally consistent with P on all vertices in D2 Y D3 .6

3.5

An Equivalence Relation on Graphs

Consider two partially labeled graphs H and H1 with poles S “ pv1 , . . . , vp q and S 1 “ pv11 , . . . , vp1 q, respectively.
Let ξpH, Sq “ pD1 , D2 , D3 q and ξpH1 , S 1 q “ pD11 , D21 , D31 q. Define Q “ pQ, Lq and Q1 “ pQ1 , L1 q as the
subgraphs of H and H1 induced by the vertices in D1 Y D2 and D11 Y D21 , respectively.
‹
The relation pH, Sq „ pH1 , S 1 q holds if and only if there is a 1-1 correspondence φ : pD1 YD2 q Ñ pD11 YD21 q
meeting the following conditions.
Isomorphism. The two graphs Q and Q1 are isomorphic under φ. Moreover, for each v P D1 Y D2 and its
corresponding vertex v 1 “ φpvq P D11 Y D21 , (i) Lpvq “ L1 pv 1 q, (ii) if the underlying LCL problem has
input labels, then the input labels of v and v 1 are the same, and (iii) v is the ith pole in S iff v 1 is the
ith pole in S 1 .
Extendibility. Let L˚ be any assignment of output labels to vertices in D1 Y D2 and let L1˚ be the corresponding labeling of D11 Y D21 under φ. Then L˚ is extendible to V pHq if and only if L1˚ is extendible
to V pH 1 q.
Notice that there could be many 1-1 correspondences between D1 Y D2 and D11 Y D21 that satisfy the isomorphism requirement, though only some subset may satisfy the extendibility requirement due to differences
in the topology and partial labeling of D3 and D31 . Any φ meeting both requirements is a witness of the
‹
relation pH, Sq „ pH1 , S 1 q.

3.6

Properties of the Equivalence Relation
1

Let G “ ReplacepG, pH, Sq, pH1 , S 1 qq. Consider the partitions ξpH, Sq “ pD1 , D2 , D3 q and ξpH1 , S 1 q “
pD11 , D21 , D31 q and let D0 “ V pGq ´ V pHq and D01 “ V pG1 q ´ V pH 1 q be the remaining vertices in G and
G1 , respectively.
‹
If pH, Sq „ pH1 , S 1 q then there exists a 1-1 correspondence φ : pD0 Y D1 Y D2 q Ñ pD01 Y D11 Y D21 q such
that (i) φ restricted to D0 is the natural 1-1 correspondence between D0 and D01 and (ii) φ restricted to
‹
D1 Y D2 witnesses the relation pH, Sq „ pH1 , S 1 q. Such a 1-1 correspondence φ is called good. We have the
following lemma.
6 We are not concerned whether L is consistent with P for vertices in D . Ultimately, H will be a subgraph of a larger
˛
1
graph G. Since the r-neighborhoods of vertices in D1 will intersect V pGq ´ V pHq, the labeling of H does not provide enough
information to tell if these vertices’ r-neighborhoods will be consistent with P. See Figure 3.

10

Lemma 1. Let G 1 “ ReplacepG, pH, Sq, pH1 , S 1 qq. Consider the partitions ξpH, Sq “ pD1 , D2 , D3 q and
‹
ξpH1 , S 1 q “ pD11 , D21 , D31 q and let D0 “ V pGq ´ V pHq and D01 “ V pG1 q ´ V pH 1 q. Suppose that pH, Sq „
1
1
1
1
1
pH , S q, so there is a good 1-1 correspondence φ : pD0 Y D1 Y D2 q Ñ pD0 Y D1 Y D2 q. Let L˛ be a complete
labeling of G that is locally consistent for all vertices in D2 Y D3 . Then there exists a complete labeling L1˛
of G 1 such that the following conditions are met.
Condition 1. L˛ pvq “ L1˛ pv 1 q for each v P D0 Y D1 Y D2 and its corresponding vertex v 1 “ φpvq P D01 Y
D11 Y D21 . Moreover, if L˛ is locally consistent for v, then L1˛ is locally consistent for v 1 .
Condition 2. L1˛ is locally consistent for all vertices in D21 Y D31 .
Proof. We construct L1˛ as follows. First of all, for each v P D0 Y D1 Y D2 , fix L1˛ pφpvqq “ L˛ pvq. It remains
to show how to assign output labels to vertices in D31 to meet Conditions 1 and 2.
Let L˚ be L˛ restricted to the domain D1 Y D2 . Similarly, let L1˚ be L1˛ restricted to D11 Y D21 . Due to
the fact that L˛ is locally consistent for all vertices in D2 Y D3 , the labeling L˚ is extendible to all of H.
‹
Since pH, Sq „ pH1 , S 1 q, the labeling L1˚ must also be extendible to all of H1 . Thus, we can set L1˛ pv 1 q for all
1
1
v P D3 in such a way that L1˛ is locally consistent for all vertices in D21 Y D31 . Therefore, Condition 2 is met.
To see that (the second part of) Condition 1 is also met, observe that for v P D0 Y D1 , N r pvq Ď
D0 Y D1 Y D2 . Therefore, if L˛ is locally consistent for v P D0 Y D1 , then L1˛ is locally consistent for φpvq
since they have the same radius-r neighborhood view. Condition 2 already guarantees that L1˛ is locally
consistent for all v 1 P D21 .7
Theorem 3 provides a user-friendly corollary of Lemma 1, which does not mention the tripartition ξ.
‹

Theorem 3. Let G “ pG, Lq and H “ pH, Lq be a subgraph G. Suppose H1 is a graph for which pH, Sq „
pH1 , S 1 q and let G 1 “ ReplacepG, pH, Sq, pH1 , S 1 qq. We write G 1 “ pG1 , L1 q and H1 “ pH 1 , L1 q. Let L˛ be a
complete labeling of G that is locally consistent for all vertices in H. Then there exists a complete labeling
L1˛ of G 1 such that the following conditions are met.
• For each v P V pGq ´ V pHq and its corresponding v 1 P V pG1 q ´ V pH 1 q, we have L˛ pvq “ L1˛ pv 1 q.
Moreover, if L˛ is locally consistent for v, then L1˛ is locally consistent for v 1 .
• L1˛ is locally consistent for all vertices in H 1 .
Theorem 3 has several useful consequences. If L˛ is a legal labeling of G, then the output labeling L1˛ of G 1
guaranteed by Theorem 3 is also legal. Observe that setting G “ H in Theorem 3 implies G 1 “ H1 . Suppose
‹
that H admits a legal labeling. For any pH1 , S 1 q such that pH1 , S 1 q „ pH, Sq, the partially labeled graph H1
also admits a legal labeling. Thus, whether H admits a legal labeling is determined by the equivalence class
of pH, Sq (for any choice of S).
Roughly speaking, Theorem 4 shows that the equivalence class of pG, Xq is preserved after replacing a
‹
subgraph H of G by another partially labeled graph H1 such that pH, Sq „ pH1 , S 1 q.
‹

Theorem 4. Let G “ pG, Lq and let H “ pH, Lq be a subgraph G. Suppose H1 is such that pH, Sq „ pH1 , S 1 q
for some pole lists S, S 1 . Let G 1 “ ReplacepG, pH, Sq, pH1 , S 1 qq be a partially labeled graph. Designate a set
X Ď pV pGq ´ V pHqq Y S as the poles of G, listed in some order, and let X 1 be the corresponding list of
‹
vertices in G 1 . It follows that pG, Xq „ pG 1 , X 1 q.
Proof. Consider the four partitions ξpH, Sq “ pB1 , B2 , B3 q, ξpH1 , S 1 q “ pB11 , B21 , B31 q, ξpG, Xq “ pD1 , D2 , D3 q,
and ξpG 1 , X 1 q “ pD11 , D21 , D31 q. We write B0 “ V pGq´V pHq and B01 “ V pG1 q´V pH 1 q. Let φ be any good 1-1
correspondence from B0 Y B1 Y B2 to B01 Y B11 Y B21 . Because X Ď B0 Y S, we have D1 Y D2 Ď B0 Y B1 Y B2
‹
and D11 Y D21 Ď B01 Y B11 Y B21 . To show that pG, Xq „ pG 1 , X 1 q, it suffices to prove that φ (restricted to the
‹
domain D1 Y D2 ) is a witness to the relation pG, Xq „ pG 1 , X 1 q.
1
Let L˚ : pD1 Y D2 q Ñ Σout and L˚ be the corresponding labeling of D11 Y D21 . All we need to do is show
that L˚ is extendible to all of V pGq if and only if L1˚ is extendible to all of V pG1 q. Since we can also write
7 It is this lemma that motivates our definition of the tripartition ξpH, Sq. It is not clear how an analogue of Lemma 1 could
be proved using the seemingly more natural bipartition, i.e., by collapsing D1 , D2 into one set.

11

G “ ReplacepG 1 , pH1 , S 1 q, pH, Sqq, it suffices to show just one direction, i.e., if L˚ is extendible then L1˚ is
extendible.
Suppose that L˚ is extendible. Then there exists an output labeling L˛ of G such that (i) for each
v P D1 Y D2 , we have L˚ pvq “ L˛ pvq, and (ii) L˛ is locally consistent for all vertices in D2 Y D3 . Observe
that D2 Y D3 Ě B2 Y B3 . By Lemma 1, there exists a complete labeling L1˛ of G 1 such that the two conditions
in Lemma 1 are met. We show that this implies that L1˚ is extendible.
Lemma 1 guarantees that L˛ pvq “ L1˛ pφpvqq for each v P B0 Y B1 Y B2 and its corresponding vertex
φpvq P B01 Y B11 Y B21 . Since D11 Y D21 Ď B01 Y B11 Y B21 , we have L1˚ pv 1 q “ L1˛ pv 1 q for each v 1 P D11 Y D21 .
Since L˛ is locally consistent for all vertices in D2 Y D3 , Lemma 1 guarantees that L1˛ is locally consistent
for all vertices in D21 Y D31 . More precisely, due to Condition 1, L1˛ is locally consistent for all vertices in
pD21 Y D31 q ´ B31 ; due to Condition 2, L1˛ is locally consistent for all vertices in B21 Y B31 .
Thus, L1˚ is extendible, as the complete labeling L1˛ of G 1 satisfies: (i) for each v 1 P D11 Y D21 , we have
1
L˚ pv 1 q “ L1˛ pv 1 q, and (ii) L1˛ is locally consistent for all vertices in D21 Y D31 .

3.7

The Number of Equivalence Classes
‹

An important feature of „ is that it has a constant number of equivalence classes, for any fixed number p of
poles. Which constant is not important, but we shall work out an upper bound nonetheless.8
Consider a partially labeled graph H with poles S “ pv1 , . . . , vp q. Let ξpH, Sq “ pD1 , D2 , D3 q and define
Q “ pQ, Lq to be the subgraph of H induced by D1 Y D2 . Observe that the equivalence class of pH, Sq
is determined by (i) the topology of Q (including its input labels from Σin , if P has input labels), (ii) the
locations of the poles S Ď V pQq in Q, and (iii) the subset of all output labelings of V pQq “ D1 Y D2 that
are extendible.
The number of vertices in D1 Y D2 is at most p∆2r . The total number of distinct graphs of at most
p∆2r
p∆2r
p∆2r vertices (with input labels from Σ and a set of p designated poles) is at most 2p 2 q |Σ |
.
in

in

p∆2r

The total number of output labelings of D1 Y D2 is at most |Σout |
. Therefore, the total number of
2r
p∆2r
p∆2r
p∆
|Σ
p
q
, which is constant whenever
equivalence classes of graphs with p poles is at most 2 2 |Σin |
2 out |
∆, r, |Σin | , |Σout |, and p are.

3.8

A Pumping Lemma for Trees

In this section we consider partially labeled trees with one and two poles; they are called unipolar (or rooted )
and bipolar, respectively. Let T “ pT, Lq be a unipolar tree with pole list S “ pzq, z P V pT q. Define ClasspT q
‹
to be the equivalence class of pT , Sq w.r.t. „. Notice that whether a partially labeled rooted tree T admits
a legal labeling is determined by ClasspT q (Theorem 3). We say that a class is good if each partially labeled
rooted tree in the class admits a legal labeling; otherwise the class is bad. We write C to denote the set of
all classes. Notice that |C | is constant. The following lemma is a specialization of Theorem 4.
Lemma 2. Let T be a partially labeled rooted (unipolar) tree, and let T 1 be a rooted subtree of T , whose
leaves are also leaves of T . Let T 2 be another partially labeled rooted tree such that ClasspT 1 q “ ClasspT 2 q.
Then replacing T 1 with T 2 does not alter the class of T .
Let H “ pH, Lq be a bipolar tree with poles S “ ps, tq. The unique oriented path in H from s to t is
called the core path of H. It is more convenient to express a bipolar tree as a sequence of rooted/unipolar
trees, as follows. The partially labeled bipolar tree H “ pTi qiPrks is formed by arranging the roots of unipolar
trees pTi q into a path P “ pv1 , . . . , vk q, where vi is the root/pole of Ti . The two poles of H are s “ v1 and
‹
t “ vk , so P is the core path of H. Define TypepHq as the equivalence class of pH, S “ ps, tqq w.r.t. „. The
following lemma follows from Theorem 4.
Lemma 3. Let H be a partially labeled bipolar tree with poles ps, tq. Let T be H, but regarded as a unipolar
tree rooted at s. Then ClasspT q is determined by TypepHq. If we write H “ pTi qiPrks , then TypepHq is
determined by ClasspT1 q, . . . , ClasspTk q.
8 For the sake of simplicity, in the calculation we assume that the underlying LCL problem does not refer to port-numbering.
It is straightforward to see that even if port-numbering is taken into consideration, the number of equivalence classes (for any
fixed p) is still a constant.

12

Let G “ pG, Lq be a partially labeled graph, and let H “ pH, Lq be a bipolar subtree of G with poles
ps, tq. Let H1 be another partially labeled bipolar tree. Recall that G 1 “ ReplacepG, H, H1 q is defined as the
partially labeled graph resulting from replacing the subgraph H with H1 in G. We write G 1 “ pG1 , L1 q and
H1 “ pH 1 , L1 q. The following lemmas follow from Theorems 3 and 4.
Lemma 4. Consider G 1 “ ReplacepG, H, H1 q. If TypepH1 q “ TypepHq and G admits a legal labeling L˛ , then
G 1 admits a legal labeling L1˛ such that L˛ pvq “ L1˛ pv 1 q for each vertex v P V pGq ´ V pHq and its corresponding
v 1 P V pG1 q ´ V pH 1 q.
Lemma 5. Suppose that G “ pTi qiPrks is a partially labeled bipolar tree, H “ pTi , . . . , Tj q is a bipolar subtree of
G, and H1 is some other partially labeled bipolar tree with TypepH1 q “ TypepHq. Then G 1 “ ReplacepG, H, H1 q
is a partially labeled bipolar tree and TypepG 1 q “ TypepGq.
Lemma 6. Let H “ pTi qiPrks and H1 “ pTi qiPrk`1s be identical to H in its first k trees. Then TypepH1 q is a
function of TypepHq and ClasspTk`1 q.
Lemma 6 is what allows us to bring classical automata theory into play. Suppose that we somehow
computed and stored ci “ ClasspTi q at the root of Ti . Lemma 6 implies that a finite automaton walking
along the core path of H1 “ pTi qiPrk`1s , can compute TypepH1 q, by reading the vector pc1 , . . . , ck`1 q one
character at a time. The number of states in the finite automaton depends only on the number of types
(which is constant) and is independent of k ` 1 and the size of the individual trees pTi q. Define `pump “ Op1q
as the number of states in this finite automaton. The following pumping lemma for bipolar trees is analogous
to the pumping lemma for regular languages.
Lemma 7. Let H “ pT1 , . . . , Tk q, with k ě `pump . We regard each Ti in the string notation H “ pT1 , . . . , Tk q
as a character. Then H can be decomposed into three substrings H “ x ˝ y ˝ z such that (i) |xy| ď `pump ,
(ii) |y| ě 1, and (iii) Typepx ˝ y j ˝ zq “ TypepHq for each non-negative integer j.
We will use Lemma 7 to expand the length of the core path of a bipolar tree to be close to a desired
target length w. The specification for the function Pump is as follows.
Pump Let H “ pTi qiPrks be a partially labeled bipolar tree with k ě `pump . PumppH, wq produces a partially
labeled bipolar tree H1 “ pTi1 qiPrk1 s such that (i) TypepHq “ TypepH1 q, (ii) k 1 P rw, w ` `pump s, and (iii)
if we let Z “ tTi uiPrks (resp., Z 1 “ tTi1 uiPrk1 s ) be the set of rooted trees appearing in the tree list of H
(resp., H1 ), then Z 1 “ Z.
By Lemma 7, such a function Pump exists.

3.9

Rake & Compress Graph Decomposition

In this section we describe an Oplog nq-round DetLOCAL algorithm to decompose the vertex set V pGq of
a tree into the disjoint union V1 Y ¨ ¨ ¨ Y VL , L “ Oplog nq. Our algorithm is inspired by Miller and Reif’s
parallel tree contraction [32]. We first describe the decomposition algorithm then analyze its properties.
Fix the constant ` “ 2pr ` `pump q, where r, `pump depend on the LCL problem P. In the postprocessing
step of the decomposition algorithm we compute an p`, 2`q-independent set, in Oplog˚ nq time [31], defined
as follows.
Definition 1. Let P be a path. A set I Ă V pP q is called an pα, βq-independent set if the following conditions
are met: (i) I is an independent set, and I does not contain either endpoint of P , and (ii) each connected
component induced by V pP q ´ I has at least α vertices and at most β vertices, unless |V pP q| ă α, in which
case I “ H.
The Decomposition Algorithm. The algorithm begins with U “ V pGq and i “ 1, repeats Steps 1–3
until U “ H, then executes the Postprocessing step.
1. For each v P U :
(a) Compress. If v belongs to a path P such that |V pP q| ě ` and degU puq “ 2 for each u P V pP q,
then tag v with iC .
13

(b) Rake. If degU pvq “ 0, then tag v with iR . If degU pvq “ 1 and the unique neighbor u of v in U
satisfies either (i) degU puq ą 1 or (ii) degU puq “ 1 and IDpvq ą IDpuq, then tag v with iR .
2. Remove from U all vertices tagged iC or iR .
3. i Ð i ` 1.
Postprocessing Step. Initialize Vi as the set of all vertices tagged iC or iR . At this point the graph
induced by Vi consists of unbounded length paths, but we prefer constant length paths. For each edge tu, vu
such that v is tagged iR and u is tagged iC , promote v from Vi to Vi`1 . For each path P that is a connected
component induced by vertices tagged iC , compute an p`, 2`q-independent set IP of P , and then promote
every vertex in IP from Vi to Vi`1 .9
Properties of the Decomposition. As we show below, L “ Oplog nq iterations suffice, i.e., V pGq “
V1 Y ¨ ¨ ¨ Y VL . The following properties are easily verified.
ŤL
• Define Gi as the graph induced by vertices at level i or above: j“i Vj . For each v P Vi , degGi pvq ď 2.
• Define Pi as the set of connected components (paths) induced by vertices in Vi that contain more than
one vertex. For each P P Pi , ` ď |V pP q| ď 2` and degGi pvq “ 2 for each vertex v P V pP q.
• The graph GL contains only isolated vertices, i.e., PL “ H.
As a consequence, each vertex v P Vi falls into exactly one of two cases: (i) v has degGi pvq ď 1 and has
no neighbor in Vi , or (ii) v has degGi pvq “ 2 and is in some path P P Pi .
Analysis. We prove that for L “ Oplog1`1{` nq “ Oplog nq, L iterations of the graph decomposition
routine suffices to decompose any n-vertex tree. Each iteration of the routine takes Op1q time, and the
p`, 2`q-independent set computation at the end takes Oplog˚ nq time, so Oplog nq time suffices in DetLOCAL.
Let W be the vertices of a connected component induced by U at the beginning of the ith iteration.10
We claim that at least a constant Ωp1{`q fraction of vertices in W are eliminated (i.e., tagged iC or iR ) in
the ith iteration. The proof of the claim is easy for the special case of ` “ 1, as follows. If W is not a single
edge, then all v P W with degU pvq ď 2 are eliminated. Since the degree of at least half of the vertices in
a tree is at most 2, the claim follows. In general, degree-2 paths of length less than ` are not eliminated
quickly. If one endpoint of such a path is a leaf, vertices in the path are peeled off by successive Rake steps.
Assume w.l.o.g. that |W | ą 2p` ` 1q. Define W1 “ tv P W | degU pvq “ 1u, W2 “ tv P W | degU pvq “ 2u,
and W3 “ tv P W | degU pvq ě 3u.
Case 1: |W2 | ě
|W3 | ´ 1 ă
p`´1q|W |
.
``1

The number of connected components induced by vertices in W2 is at most |W1 | `
The number of vertices in W2 that are not tagged iC during Compress is less than

Therefore, at least

Case 2: |W2 | ă
least

`|W |
``1 .
|W |
``1 .

|W |
2p``1q

`|W |
``1 .

`|W |
``1

´

p`´1q|W |
``1

“

|W |
``1

vertices are tagged iC by Compress.

In any tree |W1 | ą |W3 |, so |W1 | ą

|W1 |`|W3 |
2

“

|W |´|W2 |
2

ě

|W |
2p``1q .

Therefore, at

vertices are tagged iR by Rake.

Hence the claim follows.

3.10

Extend and Label Operations

In this section we define two operations Extend and Label which are used extensively in Sections 3.11—3.12.
The operation Extend is parameterized by a target length w ě ` “ 2pr ` `pump q. The operation Label is
parameterized by a function f which takes a partially labeled bipolar tree H as input, and assigns output
labels to the vertices in v P N r´1 peq, where e is the middle edge in the core path of H.11
9 The set V in the graph decomposition is analogous to (but clearly different from) the set V defined in the Hierarchical
i
i
2 12 -coloring problem from Section 2.
10 In general, the graph induced by U is a forest. It is simpler to analyze a single connected component W .
11 By definition, if e “ tx, yu then N r´1 peq “ N r´1 pxq Y N r´1 pyq.

14

Figure 4: Left: A bipolar subtree H is attached to the rest of the graph G via edges tu, su, tv, tu. The pink
nodes have been pre-committed to output labels by Label (r “ 1). Right: The Duplicate-Cut operation
duplicates H and attaches one copy to u and the other to v.
Label. Let H “ pT1 , . . . , Tx q be a partially labeled bipolar tree with x ě `. Let pv1 , . . . , vx q be the core path
of H and e “ tvtx{2u , vtx{2u`1 u be the middle edge of the core path. It is guaranteed that all vertices in
N r´1 peq in H are not already assigned output labels. The partially labeled bipolar tree H1 “ LabelpHq
is defined as the result of assigning output labels to vertices in N r´1 peq by the function f .12
Extend. Let H “ pT1 , . . . , Tx q be a partially labeled bipolar tree with x P r`, 2ws. The partially labeled
bipolar tree H1 “ ExtendpHq is defined as follows. Consider the decomposition H “ X ˝ Y ˝ Z, where
Y “ pTtx{2u´r`1 , . . . , Ttx{2u`r q. Then H1 “ PumppX , wq ˝ Y ˝ PumppZ, wq.
Intuitively, the goal of the operation Extend is to extend the length of the core path of H while preserving
the type of H, due to Lemma 5. Suppose that the number of vertices in the core path of H is in the range
r`, 2`s. The prefix X and suffix Z are stretched to lengths in the range rw, w ` `pump s, and the middle part
Y has length 2r, so the core path of H1 has length in the range r2pw ` rq, 2pw ` r ` `pump qs.
The reason that the Extend operation does not modify the middle part Y is to ensure that (given any
labeling function f ) the type of H1 “ ExtendpLabelpHqq is invariant over all choices of the parameter w.13
We have the following lemma.
Lemma 8. Let G “ pG, Lq be a partially labeled graph and H “ pH, Lq be a bipolar subtree of G with poles
ps, tq. Let H̃ be another partially labeled bipolar tree with TypepH̃q “ TypepHq and H1 “ ExtendpLabelpH̃qq. If
G 1 “ ReplacepG, H, H1 q admits a legal labeling L1˛ , then G admits a legal labeling L˛ such that L˛ pvq “ L1˛ pv 1 q
for each vertex v P V pGq ´ V pHq and its corresponding vertex v 1 P V pG1 q ´ V pH 1 q.
Proof. Recall that the operation Extend guarantees that TypepExtendpH̃qq “ TypepH̃q “ TypepHq. Define
H2 “ ExtendpH̃q and G 2 “ ReplacepG, H, H2 q. Observe that H1 “ ExtendpLabelpH̃qq can be seen as the
result of fixing the output labels of some unlabeled vertices in H2 “ ExtendpH̃q. Therefore, L1˛ is also a legal
labeling of G 2 . By Lemma 4, the desired legal labeling L˛ of G “ ReplacepG 2 , H2 , Hq can be obtained from
the legal labeling L1˛ of G 2 .
In addition to Extend and Label, we also modify trees using the Duplicate-Cut operation, defined below.
Duplicate-Cut. Let G “ pG, Lq be a partially labeled graph and H “ pH, Lq be a bipolar subtree with poles
ps, tq. Suppose that H is connected to the rest of G via two edges tu, su and tv, tu. The partially
labeled graph G 1 “ Duplicate-CutpG, Hq is formed by (i) duplicating H and the edges tu, su, tv, tu so
that u and v are attached to both copies of H, (ii) removing the edge that connects u to one copy of
H, and removing the edge from v to the other copy of H.
12 Note that the neighborhood function is evaluated w.r.t. H.
In particular, the set N r´1 peq contains the vertices
vtx{2u´r`1 , . . . , vtx{2u`r of the core path, and also contains parts of the trees Ttx{2u´r`1 , . . . , Ttx{2u`r .
13 Notice that Extend is applied after Label. Thus, the vertices that are assigned output labels during Label must be within
the middle part Y, no part of which is modified during Extend.

15

Later on we will see that both poles of a bipolar tree are responsible for computing the labeling of the
tree. On the other hand, we do not want the poles to have to communicate too much. As Lemma 9 shows,
the Duplicate-Cut operation (in conjunction with Extend and Label) allows both poles to work independently
and cleanly integrate their labelings afterward.
Lemma 9. Let H “ ExtendpLabelpH̃qq for some partially labeled bipolar tree H̃. If G 1 “ Duplicate-CutpG, Hq
admits a legal labeling L1˛ , then G admits a legal labeling L˛ such that L˛ pvq “ L1˛ pv 1 q for each vertex
v P V pGq ´ V pHq and a particular corresponding vertex v 1 in G 1 .
Proof. Let G 1 “ pG1 , L1 q. We write H “ pT1 , . . . , Tx q. Let pv1 , . . . , vx q be the core path of H, where s “ v1
and t “ vx are the two poles of H. Let tu, su and tv, tu be the two edges that connect H two the rest of G.
Let e “ tvj , vj`1 u be the edge in the core path of H such that the output labels of vertices in N r´1 peq in H
were fixed by Label.14 We write Hu (resp., Hv ) to denote the copy of H in G 1 that attaches to u (resp., v).
Define a mapping φ from V pGq to V pG1 q as follows.
• For z P V pGq ´ V pHq, φpzq is the corresponding vertex in G1 .
Ťj
• For z P i“1 Ti , φpzq is the corresponding vertex in Hu .
Ťx
• For z P i“j`1 Ti , φpzq is the corresponding vertex in Hv .
We set L˛ pzq “ L1˛ pφpzqq for each z P V pGq. It is straightforward to verify that the distance-r neighborhood
view (with output labeling L˛ ) of each vertex z P V pGq is the same as the distance-r neighborhood view
(with output labeling L1˛ ) of its corresponding vertex φpzq in G1 . Thus, L˛ is a legal labeling.
Notice that in the proof of Lemma 9, the only property of H that we use is that N r´1 peq was assigned
output labels in the application of LabelpH̃q.

3.11

A Hierarchy of Partially Labeled Trees

In this section we construct several sets of partially labeled unipolar and bipolar trees—tT
i u, tHi u, and
Ť
tHi` u, i P Z` —using the operations Extend and Label. If each member of T ‹ “ i Ti admits a legal
labeling, then we can use these trees to design an Oplog nq-time DetLOCAL algorithm for P. Each T P T ‹ is
partially labeled in the following restricted manner. The tree T “ pT, Lq has a set of designated edges such
that Lpvq ‰ K is defined if and only if v P N r´1 peq for some designated edge e; these vertices were issued
labels by some invocation of Label.
The sets of bipolar trees tHi uiPZ` and tHi` uiPZ` and unipolar trees tTi uiPZ` are defined inductively.
In the base case we have T1 “ tT u, where T is the unique unlabeled, single-vertex, unipolar tree.
T Sets: For each i ą 1, Ti consists of all partially labeled rooted trees T formed in the following manner.
The root z of T has degree 0 ď degpzq ď ∆. Each child of z is either (i) the root of a partially labeled
rooted tree T 1 from Ti´1 (having degree at most ∆ ´ 1), or (ii) one of the two poles of a bipolar tree
`
H from Hi´1
.
H Sets: For each i ě 1, Hi contains all partially labeled bipolar trees H “ pTj qjPrxs such that x P r`, 2`s,
and for each j P rxs, Tj P Ti , where the root of Tj has degree at most ∆ ´ 2. For example, since
T1 contains only the single-vertex unlabeled tree, H1 is the set of all bipolar, unlabeled paths with
between ` and 2` vertices.
H ` Sets: For each i ě 1, Hi` is constructed by the following procedure. If i “ 1, initialize H1` Ð H,
`
otherwise initialize Hi` Ð Hi´1
. Consider each H P Hi in some canonical order. If there does not
already exist a partially labeled bipolar tree H̃ such that TypepH̃q “ TypepHq and ExtendpLabelpH̃qq P
Hi` , then update Hi` Ð Hi` Y tExtendpLabelpHqqu.
14 Because Pump usually does not extend X and Z by precisely the same amount, the edge e is generally not exactly in the
middle.

16

Observe that whereas tTi u and tHi u grow without end, and contain arbitrarily large trees, the cardinality of
Hi` is at most the total number of types, which is constant.15 This is due to the observation that whenever
we add a new partially labeled bipolar tree ExtendpLabelpHqq to Hi` , it is guaranteed that there is no other
partially labeled bipolar tree ExtendpLabelpH̃qq P Hi` such that TypepH̃q “ TypepHq. The property that
|Hi` | is constant is crucial in the proof of Lemma 16. Lemmas 10–12 reveal some useful properties of these
sets.
Lemma 10. We have (i) T1 Ď T2 Ď ¨ ¨ ¨ , (ii) H1 Ď H2 Ď ¨ ¨ ¨ , and (iii) H1` Ď H2` Ď ¨ ¨ ¨ .
Proof. By construction, we already have H1` Ď H2` Ď ¨ ¨ ¨ . Due to the construction of Hi from the set
Ti , it is guaranteed that if Tj Ď Tj`1 holds then Hj Ď Hj`1 holds as well. Thus, it suffices to show that
T1 Ď T2 Ď ¨ ¨ ¨ . This is proved by induction.
For the base case, we have T1 Ď T2 because T2 also contains T P T1 , the unlabeled, single-vertex,
unipolar tree.
For the inductive step, suppose that we already have T1 Ď T2 Ď ¨ ¨ ¨ Ď Ti , i ě 2. Then we show that
Ti Ď Ti`1 . Observe that the set Ti`1 contains all partially labeled rooted trees constructed by attaching
`
`
partially labeled trees from the sets Hi` and Ti to the root vertex. We already know that Hi´2
Ď Hi´1
,
and by the inductive hypothesis we have Ti´2 Ď Ti´1 . Thus, each T P Ti must also appear in the set
Ti`1 .
If T and H are arbitrary sets of unipolar and bipolar trees, we define ClasspT q “ tClasspT q | T P T u
and TypepH q “ tTypepHq | H P H u to be the set of classes and types appearing among them.
Lemma 11. Define k ‹ “ |C |, where C is the set of all classes. Then ClasspT ‹ q “ ClasspTk‹ q.
`
Proof. For each i ą 1, ClasspTi q depends only on TypepHi´1
q and ClasspTi´1 q, due to Lemmas 2 and 3. Let
˚
i be the smallest index such that ClasspTi˚ q “ ClasspTi˚ `1 q. Then we have TypepHi˚ q “ TypepHi˚ `1 q
and as a consequence, Hi˚` “ Hi˚``1 . This implies that ClasspTi˚ `1 q “ ClasspTi˚ `2 q. By repeating the
same argument, we conclude that for each j ě i˚ , we have ClasspTj q “ ClasspTi˚ q “ ClasspT ‹ q. Since
T1 Ď T2 Ď . . . (Lemma 10), we have i˚ ď |C |.

Lemma 12. For each i, ClasspTi q does not depend on the parameter w used in the operation Extend.
Proof. Let H “ pT1 , . . . , Tx q be any partially labeled bipolar tree with x ě 2r ` 2`pump . The type of
H1 “ ExtendpHq is invariant over all choices of the parameter w. Thus, by induction, the sets ClasspTi q,
TypepHi q, and TypepHi` q are also invariant over the choice of w.
Feasible Labeling Function. In view of Lemma 12, ClasspT ‹ q depends only on the choice of the labeling
function f used by Label. We call a function f feasible if implementing Label with f makes each tree in
ClasspT ‹ q good, i.e., its partial labeling can be extended to a complete and legal labeling. In Section 3.12
we show that given a feasible function, we can generate a DetLOCAL algorithm to solve P in Oplog nq-time.
In Section 3.13, we show that (i) a feasible function can be derived from any given an nop1q -time RandLOCAL
algorithm for P, and (ii) the existence of a feasible function is decidable. These results together imply the
ωplog nq—nop1q gap. Moreover, given an LCL problem P on bounded degree trees, it is decidable whether
the RandLOCAL complexity of P is nΩp1q or the DetLOCAL complexity of P is Oplog nq.

3.12

A Oplog nq-time DetLOCAL Algorithm from a Feasible Labeling Function

In this section, we show that given a feasible function f for the LCL problem P, it is possible to design a
Oplog nq-time DetLOCAL algorithm for P on bounded degree trees.
Regardless of f , the algorithm begins by computing the graph decomposition V pGq “ V1 Y ¨ ¨ ¨ Y VL , with
L “ Oplog nq; see Section 3.9. We let the three infinite sequences tHi uiPZ` , tHi` uiPZ` , and tTi uiPZ` be
constructed with respect to the feasible f and any parameter w.
it is not necessarily true that Hi` contains at most one bipolar tree of each type. The Extend operation is
type-preserving, but this is not true of Label: TypepLabelpHqq may not equal TypepHq, so it is possible that Hi` contains two
members of the same type.
15 However,

17

A Sequence of Partially Labeled Graphs. We define below a sequence of partially labeled graphs
R1 , R2 , . . . , RL , where R1 is the unlabeled tree G (the underlying communications network), and Ri`1 is
constructed from Ri using the graph operations Extend, Label, and Duplicate-Cut. An alternative, and helpful
way to visualize Ri is that it is obtained by stripping away some vertices of G, and then grafting on some
imaginary subtrees to its remaining vertices. Formally, the graph Ri is formed by taking Gi (the subforest
ŤL
induced by j“i Vj , defined in Section 3.9), and identifying each vertex u P V pGi q with the root of a partially
labeled imaginary tree Tu,i P Ti (defined within the proof of Lemma 13). Since GL consists solely of isolated
vertices, RL is the disjoint union of trees
ŤL drawn from TL .
Once each vertex v P V pGi q “ j“i Vj in the communication network G knows Tv,i , we are able to
simulate the imaginary graph Ri in the communication network G. In particular, a legal labeling of Ri is
represented by storing the entire output labeling of the (imaginary) tree Tv,i at the (real) vertex v P V pGi q.
The official, inductive construction of Ri is described in the proof of Lemma 13.
Lemma 13. Suppose that a feasible function f is given. The partially labeled graphs R1 , . . . , RL and partially
labeled trees tTv,i | v P V pGi q, i P rLsu can be constructed in Oplog nq time meeting the following conditions.
ŤL
1. For each i P r1, Ls, each vertex v P V pGi q “ j“i Vj knows Tv,i P Ti .
2. For each i P r2, Ls, given a legal labeling of Ri , a legal labeling of Ri´1 can be computed in Op1q time.
Proof. Part (1) of the lemma is proved by induction.
Base Case. Define R1 “ G. This satisfies the lemma since Tv,1 P T1 must be the unlabeled single-vertex
tree, for each v P V pGq.
Inductive Step. We can assume inductively that Ri´1 and tTv,i´1 | v P V pGi´1 qu have been defined
and satisfy the lemma. The set Pi´1 was defined in Section 3.9. Each P P Pi´1 is a path such that
degGi´1 pvq “ 2 for each vertex v P V pP q and |V pP q| P r`, 2`s. Fix a path P “ pv1 , . . . , vx q P Pi´1 . The
bipolar graphs HP and HP` are defined as follows.
• Define HP to be the partially labelled bipolar tree pTv1 ,i´1 , . . . , Tvx ,i´1 q Notice that HP is a subgraph
of Ri´1 . Since Tvj ,i´1 P Ti´1 , for each j P rxs, it follows that HP P Hi´1 .
• Construct HP` as follows. Select the unique member H̃ P Hi´1 such that TypepH̃q “ TypepHP q and
`
`
let HP` “ ExtendpLabelpH̃qq P Hi´1
. Due to the definition of Hi´1
, such an H̃ must exist, since
HP P Hi´1 .
The partially labeled graph Ri is constructed from Ri´1 with the following three-step procedure. See Figure 5
for a schematic example of how these steps work.
Step 1. Define R1i´1 as the result of applying the following operations on Ri´1 . For each v P Vi´1 such
that Tv,i´1 is a connected component of Ri´1 , remove Tv,i´1 . Notice that a tree Tv,i´1 is a connected component of Ri´1 if and only if v’s neighborhood in G contains only vertices at lower levels:
V1 , . . . , Vi´2 .
1
Step 2. Define R`
i´1 by the following procedure. (i) Initialize G̃ Ð Ri´1 . (ii) For each P P Pi´1 , do
`
`
G̃ Ð ReplacepG̃, HP , HP q. (iii) Set Ri´1 Ð G̃.

Step 3. Define Ri by the following procedure. (i) Initialize G̃ Ð R`
i´1 . (ii) For each P P Pi´1 , do
`
G̃ Ð Duplicate-CutpG̃, HP q. (iii) Set Ri Ð G̃.
After Steps 1–3, for v P V pGi q, Tv,i is now defined to be the tree in Ri ´ pV pGi q ´ tvuq rooted at v.
Notice that the two copies of HP` generated during Step 3(ii) becomes subtrees of Tu,i and Tv,i , where u and
v are the two vertices in V pGi q adjacent to the two endpoints of P in the graph G.
We now need to verify that Ri satisfies all the claims of the lemma. Given the partially labeled graph
Ri , the partially labeled trees Tv,i for all v P V pGi q are uniquely determined. According to the construction
of Ri , each connected component of Ri ´ V pGi q must be an imaginary tree that is either (i) some Tv,j ,
18

Figure 5: Top: In this example v was a vertex in a long degree-2 path tagged pi ´ 1qC by the decomposition
procedure, and subsequently promoted to Vi . Black vertices are in Vi (or above); white vertices are in Vi´1 ;
gray vertices are in Vi´2 or below. The paths P0 “ ps0 , . . . , t0 q and P1 “ ps1 , . . . , t1 q adjacent to v have
constant length, between ` and 2`. The colored subtrees grafted onto white and gray vertices are imaginary
subtrees formed in the construction of Ri´1 . Middle: The graph is transformed by finding the graph
`
H̃b P Hi´1
, b P t0, 1u that has the same type as HPb , and replacing HPb with HP`b “ ExtendpLabelpH̃b qq.
The vertices receiving pre-committed labels are indicated in pink (r “ 1). Bottom: We duplicate HP`b ,
b P t0, 1u, and attach one of the copies of each duplicate to v. (The copies of HP`b attached to v 1 , v 2 are not
`
shown.) The tree Tv,i is the resulting tree rooted at v. Since each subtree of v is in Ti´1 or Hi´1
, it follows
that Tv,i P Ti . In this case v had no neighbors at higher levels (i ` 1 and above), so Tv,i is a connected
component of Ri . Thus, v can locally compute a legal labelling of Tv,i .

19

where v P Vj and j P t1, . . . , i ´ 1u or (ii) a copy of HP` , where P P Pj and j P t1, . . . , i ´ 1u. By induction
(and Lemma 10), for v P V1 Y ¨ ¨ ¨ Y Vj and j P t1, . . . , i ´ 1u, we have Tv,j P Tj Ď Ti´1 ; for each P P Pj
`
where j P t1, . . . , i ´ 1u, we have HP` P Hj` Ď Hi´1
. According to the inductive definition of Ti , for each
v P V pGi q we have Tv,i P Ti . This concludes the induction of Part (1).
We now turn to the proof of Part (2) of the lemma. Suppose that we have a legal labeling of Ri , where
the labeling of Tv,i is stored in v P V pGi q. We show how to compute a legal labeling of Ri´1 in Op1q time as
follows. Starting with any legal labeling L1 of Ri , we compute a legal labeling L2 of R`
i´1 , a legal labeling L3
ŤL
of R1i´1 , and finally a legal labeling L4 of Ri´1 . Throughout the process, the labels of all vertices in j“i Vj
1
are stable under L1 , L2 , L3 , and L4 . Recall that Ri , R`
i´1 , Ri´1 , and Ri´1 are all imaginary. “Time” refers
to communications rounds in the actual network G, not any imaginary graph.
From L1 to L2 . Let s, t be the poles of HP` and u, v be the vertices outside of HP` in R`
i´1 adjacent to s, t,
respectively. At this point u and v have legal labelings of Tu,i and Tv,i , both trees of which contain a
copy of HP` . Using Lemma 9 we integrate the labelings of Tu,i and Tv,i to fix a single legal labeling L2
16
of HP` in R`
i´1 .
From L2 to L3 . A legal labeling L3 of R1i´1 is obtained by applying Lemma 8. For each P P Pi´1 , the
labeling L3 on HP in R1i´1 can be determined from the labeling L2 of HP` in R`
i´1 . In greater detail,
suppose s, t are the poles of HP {HP` , which know L2 on the p2r ´ 1q-neighborhood of ts, tu in HP` . By
Lemma 8, there exists a legal labeling L3 on HP , which can be succinctly encoded by fixing L3 on the
p2r ´ 1q-neighborhoods of the roots of each unipolar tree on the core path ps “ v1 , . . . , vx “ tq of HP .
Thus, once s, t calculate L3 , they can transmit the relevant information with constant-length messages
to the roots v1 , . . . , vx . At this point each vj P Vi´1 can locally compute an extension of its labeling to
all of Tvj ,i´1 .
From L3 to L4 . Notice that Ri´1 is simply the disjoint union of R1i´1 —for which we already have a legal
labeling L3 —and each Tv,i´1 that is a connected component of Ri´1 . A legal labeling L4 of Tv,i´1 is
computed locally at v, which is guaranteed to exist since Tv,i´1 P Ti´1 .
This concludes the proof of the lemma.
Lemma 14. Let P be any LCL problem on trees with ∆ “ Op1q. Given a feasible function f , the LCL
problem P can be solved in Oplog nq time in DetLOCAL.
Proof. First compute a graph decomposition in Oplog nq time. Given the graph decomposition, for each
i P rLs, each vertex v P Vi computes the partially labeled rooted trees Tv,j for all j P ris; this can be done in
Oplog nq rounds. Since f is feasible, each partially labeled tree in T ‹ admits a legal labeling. Therefore, RL
admits a legal labeling, and such a legal labeling can be computed without communication by the vertices
in VL . Starting with any legal labeling of RL , legal labelings of RL´1 , . . . , R1 “ G can be computed in
Oplog nq additional time, using Lemma 13(2).

3.13

Existence of Feasible Labeling Function

In Lemmas 15 and 16 we show two distinct ways to arrive at a feasible labeling function. In Lemma 15 we
assume that we are given the code of a RandLOCAL algorithm A that solves P in nop1q time with at most
1{n probability of failure. Using A we can extract a feasible labeling function f .17 Lemma 15 suffices to
prove our nop1q Ñ Oplog nq speedup theorem but, because it needs the code of A, it is insufficient to answer
a more basic question. Given the description of an LCL P, is P solvable in Oplog nq time on trees or not?
Lemma 16 proves that this question is, in fact, decidable, which serves to highlight the delicate boundary
between decidable and undecidable problems in LCL complexity [5, 35].
`
is not necessary to physically store the entire L2 on HP
. To implement the following steps, it suffices that s, t both know
`
what L2 is on the subgraph induced by the p2r ´ 1q-neighborhood of ts, tu in HP
.
17 The precise running time of A influences the w parameter used by Extend. For example, if A runs in Oplog2 nq time then
w will be smaller than if A runs in n1{ log log log n time.
16 It

20

Lemma 15. Suppose that there exists a RandLOCAL algorithm A that solves P in nop1q time on n-vertex
bounded degree trees, with local probability of failure at most 1{n. Then there exists a feasible function f .
r

Proof. Define β “ |Σout |∆ to be an upper bound on the number of distinct output labelings of N r´1 peq,
where e is any edge in any graph of maximum degree ∆. Define N as the maximum number of vertices of a
tree in Tk‹ over all choices of labeling function f . As ∆, r, k ‹ are all constants, we have N “ wOp1q . Define
t to be the running time of A on a pβN ` 1q-vertex tree. Notice that t depends on N , which depends on w.
Choices of w and f . We select w to be sufficiently large such that w ě 4pr ` tq. Such a w exists since A
runs in nop1q time on an n-vertex graph, and in our case n is polynomial in w. By our choice of w, the labeled
parts of T “ pT, Lq P Tk‹ are spread far apart. In particular, (i) the sets N pr´1q`t peq for all designated
edges e in T are disjoint, (ii) for each vertex v P V pT q, there is at most one designated edge e such that the
set N r`t pvq intersects N r´1`t peq.
Let the function f be defined as follows. Take any bipolar tree H “ pH, L1 q with middle edge e on its core
path. The output labels of N r´1 peq are assigned by selecting the most probable labeling that occurs when
running A on the tree H1 “ ExtendpHq, while pretending that the underlying graph has βN ` 1 vertices.
Notice that the most probable labeling occurs with probability at least 1{β.
Proof Idea. In what follows, consider any partially labeled rooted tree T “ pT, Lq P Tk‹ , where the set
Tk‹ is constructed with the parameter w and function f . All we need to prove is that T admits a legal
labeling L˛ . Suppose that we execute A on T while pretending that the total number of vertices is βN ` 1.
Let v be any vertex in T . According to A’s specs, the probability that the output labeling of N r pvq is
inconsistent with P is at most 1{pβN ` 1q. However, it is not guaranteed that the output labeling resulting
from A is also consistent with T , since T is partially labeled. To handle the partial labeling of T , our
strategy is to consider a modified distribution of random bits generated by vertices in T that forces any
execution of A to agree with L, wherever it is defined. We will later see that with an appropriately chosen
distribution of random bits, the outcome of A is a legal labeling of T with positive probability.
Modified Distribution of Random Bits. Suppose that an execution of A on a pβN ` 1q-vertex graph
needs a b-bit random string for each vertex. For each designated edge e, let Ue be the set of all assignments
of b-bit strings to vertices in N pr´1q`t peq. Define Se as the subset of Ue such that ρ P Se if and only if the
following is true. Suppose that the b-bit string of each u P N pr´1q`t peq is ρpuq. Using the b-bit string ρpuq
for each u P N pr´1q`t peq, the output labeling of the vertices in N r´1 peq resulting from executing A is the
same as the output labeling specified by L. According to our choice of f , we must have |Se |{|Ue | ě 1{β.
Define the modified distribution D of b-bit random strings to the vertices in T as follows. For each
designated edge e, the b-bit strings of the vertices in N pr´1q`t peq are chosen uniformly at random from the
set Se . For the remaining vertices, their b-bit strings are chosen uniformly at random.
Legal Labeling L˛ Exists. Suppose that A is executed on T with the modified distribution of random
bits D. Then it is guaranteed that A outputs a complete labeling that is consistent with T . Of course, the
probability that A outputs an illegal labeling under D may be different. We need to show that A nonetheless
succeeds with non-zero probability.
Consider any vertex v P V pT q. The probability that N r pvq is inconsistent with P is at most β{pβN ` 1q
under distribution D, as explained below. Due to our choice of w, the set N r`t pvq intersects at most one
set N r´1`t peq where e is a designated edge. Let Uv be the set of all assignments of b-bit strings to vertices
in N r`t pvq. For each ρ P Uv , the probability that ρ occurs in an execution of A is 1{|Uv | if all random
bits are chosen uniformly at random, and is at most β{|Uv | under D. Thus, the probability that A (using
distribution D) labels N r pvq incorrectly is at most β{pβN ` 1q. The total number of vertices in T is at most
N . Thus, by the union bound, the probability that the output labeling of A (using D) is not a legal labeling
is βN {pβN ` 1q ă 1.
Lemma 16. Given an LCL problem P on bounded degree graphs, it is decidable whether there exists a
feasible function f .

21

Proof. Throughout the construction of the three infinite sequences tHi uiPZ` , tHi` uiPZ` , and tTi uiPZ` , the
number of distinct applications of the operation Label is constant, as |Hi` | is at most the total number of
types.
Therefore, the number of distinct candidate functions f that need to be examined is finite. For each
candidate labeling function f (with any parameter w ě `), in bounded amount of time we can construct
the set Tk‹ , as k ‹ “ |C | is a constant. By examining the classes of the partially labeled rooted trees in Tk‹
we can infer whether the function f is feasible (Lemma 11). Thus, deciding whether there exists a feasible
function f can be done in bounded amount of time.
Combining Lemmas 14, 15, and 16, we obtain the following theorem.
Theorem 5. Let P be any LCL problem on trees with ∆ “ Op1q. If there exists a RandLOCAL algorithm A
that solves P in nop1q rounds, then there exists a DetLOCAL algorithm A1 that solves P in Oplog nq rounds.
Moreover, given a description of P, it is decidable whether the RandLOCAL complexity of P is nΩp1q or the
DetLOCAL complexity of P is Oplog nq.
Remark 2. Observe that our graph decomposition algorithm also works on graphs of girth at least c log n,
where c is a sufficiently large constant depending on P. This implies that Theorem 5 also applies to the class
of n-vertex graphs with girth ωplog nq.

4

A Gap in the RandLOCAL Complexity Hierarchy

Consider a set V of independent random variables, and a set X of bad events, where A P X depends only on
some subset vblpAq Ă V of variables.18 The dependency graph GX “ pX , tpA, Bq | vblpAq X vblpBq ‰ Huq
joins events by an edge if they depend onŞat least one common variable. The Lovász local lemma (LLL) and
its variants give criteria under which Prp APX Aq ą 0, i.e., it is possible that all bad events do not occur. We
will narrow our discussion to symmetric criteria, expressed in terms of p and d, where p “ maxAPX PrpAq
andŞd is the maximum degree in GX . A standard version of the LLL states that if eppd ` 1q ă 1, then
Prp Aq ą 0. Given that all bad events can be avoided, it is often desirable to constructively find a point
in the probability space (i.e., an assignment to variables in V) that avoids them. This problem has been
thoroughly investigated in the sequential context [33, 22, 21, 26, 27, 24, 1], but somewhat less so from the
point of view of parallel and distributed computation [7, 13, 4, 6, 19].
The distributed constructive LLL problem is the following. The communications network is precisely GX .
Each vertex (event) A knows the number of bad events in GX and the distribution of those variables appearing
in vblpAq Ă V. Vertices communicate for some number of rounds, and collectively reach a consensus on an
assignment to V in which no bad event occurs. Moser and Tardos’s [33] parallel resampling algorithm
implies an Oplog2 nq time RandLOCAL algorithm under the LLL criterion eppd ` 1q ă 1. Chung, Pettie, and
Su [7] gave an Oplog1{epd2 nq time algorithm under the LLL criterion epd2 ă 1 and an Oplog n{ log log nq
time algorithm under criterion p ¨ polypdq2d “ Op1q. They observed that under any criterion of the form
p ¨ f pdq ă 1, Ωplog˚ nq time is necessary. Ghaffari’s [13] weak MIS algorithm, together with [7], implies an
Oplog d¨log1{eppd`1q nq algorithm under LLL criterion eppd`1q ă 1. Brandt et al. [4] proved that Ωplogd log nq
time in RandLOCAL is necessary, even under the permissive LLL criterion p2d ď 1. Chang et al. [6]’s results
imply that Ωplogd nq time is necessary in DetLOCAL; however, there are no known deterministic distributed
LLL algorithms. It is conceivable that the distributed complexity of the LLL is very sensitive to the criterion
used. We define TLLL pn, dq to be the RandLOCAL time to compute a point in the probability space avoiding
all bad events (w.h.p.), under any “polynomial” LLL criterion of the form
pdc “ Op1q,

(1)

where c can be an arbitrarily large constant. Prior results [7, 4] imply that TLLL pn, dq is Ωplogd log nq,
Ωplog˚ nq, and Oplog1{epd2 nq. In this section we prove an automatic speedup theorem for sublogarithmic
RandLOCAL algorithms. We do not assume that ∆ “ Op1q in this section.
18 Each

variable V P V may have a different distribution and range, so long as the range is some finite set.

22

Theorem 6. Suppose that A is a RandLOCAL algorithm that solves some LCL problem P (w.h.p.), in T∆ pnq
time. For a sufficiently small constant  ą 0, suppose T∆ pnq is upper bounded by Cp∆q `  log∆ n, for some
function C. It is possible to transform A into a new RandLOCAL algorithm A1 that solves P (w.h.p.) in
OpCp∆q ¨ TLLL pn, ∆OpCp∆qq qq time.
Proof. Suppose that A has a local probability of failure 1{n, that is, for any v P V pGq, the probability that
N r pvq is inconsistent with P is 1{n, where r is the radius of P. Once we settle on the LLL criterion exponent
c in (1), we fix  “ Opp2cq´1 q. Define n‹ as the minimum value for which
t‹ “ T∆ pn‹ q ă p1{2cq ¨ log∆ n‹ ´ r.
It follows that t‹ “ OpCp∆qq and n‹ “ ∆OpCp∆qq .
The algorithm A1 applied to an n-vertex graph G works as follows. Imagine an experiment where we
‹
run A, but lie to the vertices, telling them that “n” = n‹ . Any v P V pGq will see a t‹ -neighborhood N t pvq
that is consistent with some n‹ -vertex graph. However, the bad event that N r pvq is incorrectly labeled is
1{n‹ , not 1{polypnq, as desired. We now show that this system of bad events satisfies the LLL criterion (1).
Define the following events, graph, and quantities:
Ev : the event that N r pvq is incorrectly labeled according to P
X “ tEv | v P V pGqu
GX “ pX , tpEu , Ev q | N
d ď ∆2pr`t
p “ 1{n

‹

the set of bad events
r`t‹

puq X N

r`t‹

pvq ‰ Huq

the dependency graph

q

‹

The event Ev is determined by the labeling of N r pvq and the label of each v 1 P N r pvq is determined by
‹
‹
N t pv 1 q, hence Ev is determined by (the data stored in, and random bits generated by) vertices in N r`t pvq.
‹
‹
Clearly Ev is independent of any Eu for which N r`t puq X N r`t pvq “ H, which justifies the definition of the
‹
edge set of GX . Since the maximum degree in G is ∆, the maximum degree d in GX is less than ∆2pr`t q .
By definition of A, PrpEv q ď 1{n‹ “ p. This system satisfies LLL criterion (1) since, by definition of t‹ ,
pdc “ p∆2cpr`t

‹

q

ă p1{n‹ q ¨ n‹ “ 1.

The algorithm A1 now simulates a constructive LLL algorithm on GX in order to find a labeling such that
no bad event occurs. Since a virtual edge pEu , Ev q exists iff u and v are at distance at most 2pr ` t‹ q “
OpCp∆qq, any RandLOCAL algorithm in GX can be simulated in G with OpCp∆qq slowdown. Thus, A1 runs
in OpCp∆q ¨ TLLL pn, ∆OpCp∆qq qq time.
Theorem 6 shows that when ∆ “ Op1q, oplog nq-time RandLOCAL algorithms can be sped up to run
in OpTLLL pn, Op1qqq time. Another consequence of this same technique is that sublogarithmic RandLOCAL
algorithms with large messages can be converted to (possibly slightly slower) algorithms with small messages.
The statement of Theorem 7 reflects the use of a particular distributed LLL algorithm, namely [7, Corollary 1
and Algorithm 2]. It may be improvable using future distributed LLL technology.
The LLL algorithm of [7] works under the assumption that epd2 ă 1, and that each bad event A P X
is associated with a unique ID. The algorithm starts with a random assignment to the variables V. In each
iteration, let F be the set of bad events that occur under the current variable assignment; let I be the subset
of F such that A P I if and only if IDpAq ă IDpBq for each B PŤ
F such that vblpAq X vblpBq ‰ H. The next
variable assignment is obtained by resampling all variables in API vblpAq. After Oplog1{epd2 nq iterations,
no bad event occurs with probability 1 ´ 1{polypnq.
Theorem 7. Let A be a pCp∆q` log∆ nq-time RandLOCAL algorithm that solves some LCL problem P with
high probability, where  ą 0 is a sufficiently small constant. Each vertex locally generates r∆ pnq random
bits and sends m∆ pnq-bit messages. It is possible to transform A into a new RandLOCAL algorithm A1 that
solves P (w.h.p.) in Oplog∆ nq time, where each vertex generates Oplog n ` r∆ pζq ¨ logζ nq random bits, and
sends Opmintlogp|Σout |q ¨ ∆Op1q ` m∆ pζq ` ζ, r∆ pζq ¨ ζuq-bit messages, where ζ “ ∆OpCp∆qq depends on ∆.

23

Proof. We continue to use the notation and definitions from Theorem 6, and fix c “ 3 in the LLL criterion (1).
Since d “ Ωp∆OpCp∆qq q “ Ωpζq and we selected t‹ w.r.t. c “ 3 (i.e., LLL criterion pd3 ă 1), we have
1{epd2 “ Ωpζq. If A1 uses the LLL algorithm of [7], each vertex v P V pGq will first generate an Oplog nq-bit
unique identifier IDpEv q (which costs Oplog nq random bits) and generate r∆ pn‹ q ¨ Oplog1{epd2 nq “ Opr∆ pζq ¨
logζ nq random bits throughout the computation. Thus, the total number of random bits per vertex is
Oplog n ` r∆ pζq ¨ logζ nq.
In each resampling step of A1 , in order for v to tell whether Ev P I, it needs the following information:
‹
(i) IDpEu q for all u P N 2pr`t q pvq, and (ii) whether Eu occurs under the current variable assignment, for
‹
all u P N 2pr`t q pvq. We now present two methods to execute one resampling step of A1 ; they both take
OpCp∆qq time using a message size that depends on ∆ but is independent of n. There are Oplog1{epd2 nq “
∆n
Oplogζ nq “ Op log
Cp∆q q resampling steps, so the total time is Oplog∆ nq, independent of the function C.

Method 1. Before the LLL algorithm proper begins, we do the following preprocessing step. Each vertex
v gathers up all IDs and random bits in its 3pt‹ ` rq-neighborhood. This takes Opplog n ` r∆ pζq ¨ logζ nq ¨ ζ{bq
‹
time with b-bit messages (recall that ∆Opt `rq “ ∆OpCp∆qq “ ζ). In particular, the runtime can be made
Oplog∆ nq if we set b “ Opr∆ pζq ¨ ζq.
During the LLL algorithm, each vertex u owns one random variable: an r∆ pn‹ q-bit string Vu . In order
‹
for v to tell whether Eu occurs for each u P N 2pr`t q pvq under the current variable assignment, it only needs
‹
to know how many times each Vu , u P N 3pr`t q pvq, has been resampled. Whether the output labeling of
‹
u P N 2pr`t q pvq is locally consistent depends on the output labeling of vertices in N r puq, which depends on
‹
‹
the random bits and the graph topology within N r`t puq Ď N 3pr`t q pvq. Given the graph topology, IDs,
‹
and the random bits within N 3pr`t q pvq, the vertex v can locally simulate A and decides whether Ev P I.
Thus, in each iteration of the LLL algorithm, each vertex v simply needs to alert its 3pr`t‹ q-neighborhood
whether Vv is resampled or not. This can be accomplished in Opr ` t‹ q “ OpCp∆qq time with ζ-bit messages.
Method 2. In the second method, vertices keep their random bits private. Similar to the first method,
we do a preprocessing step to let each vertex gathers up all IDs in its 2pt‹ ` rq-neighborhood. This can be
done in Oplog∆ nq time using ζ-bit messages.
During the LLL algorithm, in order to tell which subset of bad events tEv uvPV pGq occur under the
current variable assignment, all vertices simulate A for t‹ rounds, sending m∆ pn‹ q-bit messages. After the
simulation, for a vertex v to tell whether Ev occurs, it needs to gather the output labeling of the vertices
in N r pvq. This can be done in r “ Op1q rounds, sending logp|Σout |q ¨ ∆Op1q -bit messages.19 Next, for a
‹
vertex v to tell whether Ev P I, it needs to know whether Eu occurs for all u P N 2pr`t q pvq. This information
can be gathered in OpCp∆qq time using messages of size Opζq. To summarize, the required message size is
Oplogp|Σout |q ¨ ∆Op1q ` m∆ pζq ` ζq.
An interesting corollary of Theorem 7 is that when ∆ “ Op1q, randomized algorithms with unbounded
length messages can be simulated with 1-bit messages.
Corollary 1. Let P be any LCL problem. When ∆ “ Op1q, any oplog nq algorithm solving P w.h.p. using
unbounded length messages can be made to run in Oplog nq time with 1-bit messages.

5

Conclusion

We now have a very good understanding of the LOCAL complexity landscape for cycles, tori, bounded degree
trees, and to a lesser extent, general bounded degree graphs. See Figure 1. However, there are some very
critical gaps in our understanding.
Our randomized speedup theorem of Section 4 depends on the complexity of a relatively weak version of
the Lovász local lemma. Since the LLL is essentially a “complete” problem for sublogarithmic RandLOCAL
algorithms, understanding the distributed complexity of the LLL is a significant open problem.
19 An output label can be encoded as a logp|Σ
out |q-bit string. We do not assume that ∆ is constant so |Σout |, which may
depend on ∆ but not directly on n, is also not constant. E.g., consider the Op∆q vertex coloring problem.

24

Conjecture 1. There exists a sufficiently large constant c such that the distributed LLL problem can be
solved in Oplog log nq time on bounded degree graphs, under the symmetric LLL criterion pdc ă 1.
The new polynomial complexities introduced in Section 2 are of the form Θpn1{k q, k P Z` . Is this set
of polynomial complexities exhaustive? Is it possible to engineer problems with complexity Θpnq q for any
given rational q? We think the answer is no, and resolving Conjecture 2 would be the first step.
?
Conjecture 2. Any opnq-time DetLOCAL algorithm can be automatically sped up to run in Op nq time. In
general, there is an ωpn1{pk`1q q—opn1{k q gap in the DetLOCAL complexity hierarchy.
One advantage of working with graph classes with bounded degree ∆ is that arbitrary LCLs can be
encoded in Op1q space by enumerating all acceptable configurations. To study LCLs on unbounded-degree
graphs it is probably necessary to work with logical representations of LCLs, and here the expressive power
of the logic may introduce a new measure of problem complexity. For example, the sentence “I is an MIS”
can be expressed using the predicate rv P Is and quantification over all vertices v P V pGq, and all vertices
u P N pvq.

References
[1] D. Achlioptas and F. Iliopoulos. Random walks that find perfect objects and the Lovász local lemma.
In Proceedings 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages
494–503, 2014.
[2] R. Bar-Yehuda, K. Censor-Hillel, and G. Schwartzman. A distributed p2 ` q-approximation for vertex
cover in Oplog ∆{ log log ∆q rounds. In Proceedings 35th ACM Symposium on Principles of Distributed
Computing (PODC), pages 3–8, 2016.
[3] L. Barenboim, M. Elkin, S. Pettie, and J. Schneider. The locality of distributed symmetry breaking. J.
ACM, 63, 2016. Article 20.
[4] S. Brandt, O. Fischer, J. Hirvonen, B. Keller, T. Lempiäinen, J. Rybicki, J. Suomela, and J. Uitto.
A lower bound for the distributed Lovász local lemma. In Proceedings 48th ACM Symposium on the
Theory of Computing, pages 479–488, 2016.
[5] S. Brandt, J. Hirvonen, J. H. Korhonen, T. Lempiäinen, P. R. J. Östergård, C. Purcell, J. Rybicki,
J. Suomela, and P. Uznanski. LCL problems on grids. CoRR, abs/1702.05456, 2017.
[6] Y.-J. Chang, T. Kopelowitz, and S. Pettie. An exponential separation between randomized and deterministic complexity in the LOCAL model. In Proceedings 57th Annual IEEE Symposium on Foundations
of Computer Science (FOCS), pages 615–624, 2016.
[7] K.-M. Chung, S. Pettie, and H.-H. Su. Distributed algorithms for the Lovász local lemma and graph
coloring. Distributed Computing, 2017. to appear.
[8] R. Cole and U. Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking.
Information and Control, 70(1):32–53, 1986.
[9] L. Feuilloley and P. Fraigniaud. Survey of distributed decision. CoRR, abs/1606.04434, 2016.
[10] M. Fischer and M. Ghaffari. Deterministic distributed matching: Simpler, faster, better. CoRR,
abs/1703.00900, 2017.
[11] P. Fraigniaud, A. Korman, and D. Peleg. Towards a complexity theory for local distributed computing.
J. ACM, 60(5):35:1–35:26, 2013.
[12] M. Fürer. Data structures for distributed counting. J. Comput. Syst. Sci., 28(2):231–243, 1984.
[13] M. Ghaffari. An improved distributed algorithm for maximal independent set. In Proceedings 27th
Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 270–277, 2016.
25

[14] M. Ghaffari, F. Kuhn, and Y. Maus. On the complexity of local distributed graph problems. In
Proceedings 49th ACM Symposium on Theory of Computing (STOC), 2017.
[15] M. Ghaffari and H.-H. Su. Distributed degree splitting, edge coloring, and orientations. In Proceedings
28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2505–2523, 2017.
[16] M. Göös, J. Hirvonen, and J. Suomela. Linear-in-∆ lower bounds in the LOCAL model. Distributed
Computing, pages 1–14, 2015.
[17] M. Göös and J. Suomela. Locally checkable proofs in distributed computing. Theory of Computing,
12(1):1–33, 2016.
[18] R. L. Graham, B. L. Rothschild, and J. H. Spencer. Ramsey Theory. John Wiley and Sons, New York,
2nd edition, 1990.
[19] B. Haeupler and D. G. Harris. Parallel algorithms and concentration bounds for the Lovász local
lemma via witness-DAGs. In Proceedings 28th Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA), pages 1170–1187, 2017.
[20] M. Hańćkowiak, M. Karoński, and A. Panconesi. On the distributed complexity of computing maximal
matchings. SIAM J. Discrete Mathematics, 15(1):41–57 (electronic), 2001.
[21] D. G. Harris. Lopsidependency in the Moser-Tardos framework: Beyond the lopsided Lovász local
lemma. ACM Trans. Algorithms, 13(1):17:1–17:26, 2016.
[22] D. G. Harris and A. Srinivasan. A constructive algorithm for the Lovász local lemma on permutations.
In Proceedings 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 907–925,
2014.
[23] J. Hartmanis and R. E. Stearns. On the computational complexity of algorithms. Trans. Amer. Math.
Soc., 117:285–306, 1965.
[24] N. J. A. Harvey and J. Vondrák. An algorithmic proof of the Lovász local lemma via resampling
oracles. In Proceedings 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS),
pages 1327–1346, 2015.
[25] D. Hefetz, F. Kuhn, Y. Maus, and A. Steger. Polynomial lower bound for distributed graph coloring in a
weak LOCAL model. In Proceedings 30th International Symposium on Distributed Computing (DISC),
pages 99–113, 2016.
[26] K. B. R. Kolipaka and M. Szegedy. Moser and Tardos meet Lovász. In Proceedings 43rd ACM Symposium
on Theory of Computing (STOC), pages 235–244, 2011.
[27] V. Kolmogorov. Commutativity in the algorithmic Lovász local lemma. In Proceedings 57th Annual
IEEE Symposium on Foundations of Computer Science (FOCS), pages 780–787, 2016.
[28] A. Korman, J.-S. Sereni, and L. Viennot. Toward more localized local algorithms: removing assumptions
concerning global knowledge. Distributed Computing, 26(5–6):289–308, 2013.
[29] F. Kuhn, T. Moscibroda, and R. Wattenhofer. Local computation: Lower and upper bounds. J. ACM,
63(2):17:1–17:44, 2016.
[30] F. Kuhn and R. Wattenhofer. On the complexity of distributed graph coloring. In Proceedings 25th
Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 7–15, 2006.
[31] N. Linial. Locality in distributed graph algorithms. SIAM J. Comput., 21(1):193–201, 1992.
[32] G. L. Miller and J. H. Reif. Parallel tree contraction–Part I: Fundamentals. Advances in Computing
Research, 5:47–72, 1989.

26

[33] R. A. Moser and G. Tardos. A constructive proof of the general Lovász local lemma. J. ACM, 57(2),
2010.
[34] M. Naor. A lower bound on probabilistic algorithms for distributive ring coloring. SIAM J. Discrete
Mathematics, 4(3):409–412, 1991.
[35] M. Naor and L. J. Stockmeyer. What can be computed locally? SIAM J. Comput., 24(6):1259–1277,
1995.
[36] A. Panconesi and A. Srinivasan. On the complexity of distributed network decomposition. J. Algor.,
20(2):356–374, 1996.
[37] D. Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000.
[38] J. Suomela. Survey of local algorithms. ACM Comput. Surv., 45(2):24:1–24:40, 2013.

27

A

Speedup Implications of Naor & Stockmeyer

Let A be any T pnq-round DetLOCAL algorithm. Let η and η 1 be any two order-indistinguishable assignments
of distinct IDs to N T pnq pvq, i.e., for u, w P N T pnq pvq, ηpuq ą ηpwq if and only if η 1 puq ą η 1 pwq. If, for every
possible input graph fragment induced by N T pnq pvq, the output label of v is identical under every pair of
order-indistinguishable η, η 1 , then A is order-invariant.
1
Suppose that there exists a number n1 “ Op1q such that ∆T pn q`r ď n1 . If A is order-invariant then it
1
can be turned into an Op1q-round DetLOCAL algorithm A , since we can pretend that the total number of
vertices is n1 instead of n.
Naor and Stockmeyer [35] proved that any DetLOCAL algorithm that takes τ “ Op1q rounds on a bounded
degree graph can be turned into an order-invariant τ -round DetLOCAL algorithm. A more careful analysis
shows that the proof still works when τ is a slowly growing function of n.
Requirement for Automatic Speedup. The muticolor hypergraph Ramsey number Rpp, m, cq is the
minimum number such that the following holds. Let H be a complete p-uniform hypergraph of at least
Rpp, m, cq vertices. Then any c-edge-coloring of H contains a monochromatic clique of size m.
Given the number τ ě 2, the three parameters p, m, and c are selected as follows. (See the proof of [35,
Lemma 3.2] for more details.)
• The number p is the maximum number of vertices in N τ pvq, over all vertices v P V pGq and all graphs
G under consideration. For rings, p “ 2τ ` 1. For tori, p ď 2pτ ` 1q2 . For trees or general graphs,
p ď ∆τ .
• The number m is the maximum number of vertices in N τ `r pvq, over all vertices v P V pGq and all
graphs G under consideration. E.g., for rings, p “ 2τ ` 2r ` 1 and for general graphs, p ď ∆τ `r .
• The number z counts the distinguishable radius-τ centered subgraphs, disregarding IDs. For example,
for LCLs on the ring without input labels or port numbering, z “ 1, whereas with input labels and
port numbering it is p2|Σin |q2τ `1 since each vertex has one of |Σin | input labels and 2 port numberings.
∆τ
In general z is less than 2p 2 q ¨ p∆!|Σ |qp .
in

• The number c is defined as |Σout |p!z . Intuitively, we can use a number in rcs to encode a function
that maps a radius-τ centered subgraph (that is equipped with unique vertex IDs from a set S with
cardinality p) to an output label in Σout .
Recall that vertices in DetLOCAL have Oplog nq-bit IDs, i.e., they can be viewed as elements of rnk s
for some k “ Op1q. Naor and Stockmeyer’s proof implies that, as long as nk ě Rpp, m, cq, any DetLOCAL
τ -round algorithm on a bounded degree graph can be turned into an order-invariant τ -round DetLOCAL
algorithm, which then implies an Op1q-round DetLOCAL algorithm.
According to the proof of [18, §1, Theorem 2], we have:

The Ramsey number Rpp, m, cq.
For p “ 1,
For p ą 1,

Rpp, m, cq “ cpm ´ 1q ` 1
Rpp, m, cq ď 2c

x

where x “

ˆ
Rpp´1,m,cq´1
ÿ
i“p´1

˙
i`1
ă Rpp ´ 1, m, cqp
p´1

Therefore, log˚ pRpp, m, cqq ď p ` log˚ m ` log˚ c ` Op1q.
Automatic Speedup Theorems. Observe that in all scenarios, if the running time τ “ τ pnq “ ωp1q, we
have log˚ m ` log˚ c “ oppq. Therefore, having p ď  log˚ n for some small enough constant  suffices to meet
the condition nk ě Rpp, m, cq. We conclude that the complexity of any LCL problem (with or without input

28

labels and port numbering) in the LOCAL model never falls in the following gaps:
ωp1q—oplog˚ nq
b
ωp1q—op log˚ nq

for n-rings.
?
?
for p n ˆ nq-tori.

ωp1q—oplogplog˚ nqq

for bounded degree trees or general graphs.

Due to the “Stepping-Up Lemma” (see [18, §4, Lemma 17]), we have log˚ pRpp, m, 2qq “ Ωppq. Thus, Naor
˚
and Stockmeyer’s approach alone cannot give an ωp1q—oplog
?
?nq gap for general graphs.
However, for a certain class of LCL problems on p n ˆ nq-tori, the gap can be widened to ωp1q—
oplog˚ nq [5, p. 2]. The following proof is due to Jukka Suomela (personal communication).
?
?
Theorem 8 (J. Suomela). Let P be any LCL problem on p n ˆ nq-tori that does not refer to input labels
or port-numbering. The DetLOCAL and RandLOCAL complexity of P is either Op1q or Ωplog˚ nq.
?
?
Proof. Given ?
a p n ˆ nq-torus G, we associate each vertex v P V pGq with a coordinate pα, βq, where
α, β P t0, . . . , n ´ 1u. We consider the following ?
special way to generate unique k log n-bit IDs. Let φx and
φy be two functions mapping integers
in
t0,
.
.
.
,
n ´ 1u to integers
in t0, . . . , nk{2 ´ 1u. We additionally
?
?
require that φx p0q ă . . . ă φx p n ´ 1q ă φy p0q ă . . . ă φy p n ´ 1q. If v is at position pα, βq, it has ID
φx pαq ¨ nk{2 ` φy pβq. Notice that the IDs of all vertices in N τ pvq can be deduced from just 4τ ` 2 numbers:
φx piq, i P rα ´ τ, α ` τ s and φy pjq, j P rβ ´ τ, β ` τ s.
Suppose that the complexity of P is oplog˚ nq. Let A be any τ -round DetLOCAL algorithm for solving
P, where τ “ oplog˚ nq. Notice that the algorithm A works correctly even when we restrict ourselves to the
above special ID assignment. Our goal is to show that P is actually trivial in the sense that there
? exists an
element σ P Σout such that labeling all vertices by σ gives a legal labeling, assuming w.l.o.g. that n ą 2r`1.
Thus, P can be solved in Op1q rounds.
?
In subsequent discussion,
? we let v be any vertex whose position is pα, βq, where τ ` r ď α ď p n ´ 1q ´
pτ ` rq and τ ` r ď β ď p n ´ 1q ´ pτ ` rq. That is, v is sufficiently far way from the places where the
coordinates wrap around.
Given A, we construct a function f as follows. Let S “ ps1 , . . . , s4τ `2 q be a vector of 4τ ` 2 numbers
in t0, . . . , nk{2 ´ 1u such that sk ă sk`1 for each k P r4τ ` 2s. Then f pSq P Σout is defined as the output
labeling of v resulting from executing A with the following ID assignment of vertices in N τ pvq. We set
φx pα ´ τ ´ 1 ` iq “ si for each i P r2τ ` 1s and set φy pβ ´ τ ´ 1 ` jq “ sj`2τ `1 for each j P r2τ ` 1s Recall
that P does not use port-numbering and input labeling, so the output labeling of v depends only on IDs of
vertices in N τ pvq.
We set p “ 4τ ` 2, m “ 4τ ` 4r ` 2, and c “ |Σout |. Notice that the calculation of the parameter c
here?is different from the original?proof of Naor and Stockmeyer. Since we already force that φx p0q ă . . . ă
φx p n ´ 1q ă φy p0q ă . . . ă φy p n ´ 1q, we do not need to consider all p! permutations of the set S.
We have Rpp, m, cq ! nk{2 (since p “ oplog˚ nq). Thus, there exists a set S 1 of m distinct numbers in
t0, . . . , nk{2 u such that the following is true. We label these m numbers φx piq, i P rα ´ τ ´ r, α ` τ ` rs, and
φy pjq, j P rβ ´ τ ´ r, β ` τ ` rs by the set S 1 such that φx pα ´ τ ´ rq ă . . . ă φx pα ` τ ` rq ă φy pβ ´ τ ´ rq ă
. . . ă φy pβ ` τ ` rq. Then the output labels of all vertices in N r pvq assigned by A are identical.
Therefore, there exists an element σ P Σout such that labeling all vertices by σ yields a legal labeling of
G. Thus, P can be solved in Op1q rounds.
Discussion. It still remains an outstanding open problem whether the gap for other cases can also be
widened to ωp1q—oplog˚ nq.
The proof of Theorem 8 extends easily to d-dimensional tori, but does not extend to bounded degree
trees, since there is a non-trivial problem that can be solved in Op1q rounds on a subset of bounded degree
trees. Naor and Stockmeyer [35] showed that on any graph class in which all vertex degrees are odd, weak
2Op∆ log ∆q -coloring can be solved in 2 rounds and weak 2-coloring can be solved in Oplog˚ ∆q rounds in
DetLOCAL.20 This problem is non-trivial in the sense that coloring all vertices by the same color is not a
legal solution. Since the d-dimensional torus is ∆-regular, ∆ “ 2d, we conclude that the complexity of weak
Op1q-coloring on ∆-regular graphs is Θplog˚ nq for every fixed even number ∆ ě 2.
20 A

weak coloring is one in which every vertex is colored differently than at least one neighbor.

29

Theorem 8 also does not extend to LCL problems that use input labels or port-numbering. If either input
labels or port-numbering are allowed, then one can construct a non-trivial LCL problem that can be solved
in Op1q rounds even on cycle graphs. An orientation of a vertex v P V pGq is defined as a port-number in
rdegpvqs, indicating a vertex in N pvq that v is pointed towards. An `-orientation of a cycle G is an orientation
of all vertices in G meeting the following conditions. If |V pGq| ď `, then all vertices in G are oriented to
the same direction, i.e., no two vertices point toward each other. If |V pGq| ą `, then each vertex v P V pGq
belongs to a path P such that (i) all vertices in P are oriented to the same direction (no two point to each
other), and (ii) the number of vertices in P is at least `. Notice that `-orientation, ` “ Op1q, is an LCL
that refers to port-numbering. We show that in Op1q rounds we can compute an `-orientation of G for any
constant `.21
Theorem 9. Let G be a cycle graph and ` be a constant. There is a DetLOCAL algorithm that computes an
`-orientation of G in Op1q rounds.
Proof. This is a known result. See [20, Fact 5.2] or [10, Lemma 3.6, Case B] for a sketch of the proof. For
the sake of completeness, we present a full proof. We first show how to compute a 2-orientation of a cycle G
in Op1q rounds, and then we extend it to any constant `.
Computing a 2-orientation. We assume |V pGq| ě 3. A DetLOCAL Op1q-round algorithm to compute a
2-orientation is described as follows. First, each vertex v P V pGq computes an arbitrary orientation. With
respect to this orientation of G, define sets V1 , V2 , V3 as follows.
• v P V1 if and only if there exists u P N pvq such that u and v are oriented to the same direction.
• v P V2 if and only if there exists u P N pvqzV1 such that u and v are oriented toward each other.
• V3 “ V pGqzpV1 Y V2 q. Observe that for each v P V3 , there exists u P N pvq X V1 .
A 2-orientation is obtained by re-orienting the vertices in V2 and V3 . The vertices in V2 are partitioned into
unordered pairs such that u, v P V2 are paired-up if and only if (i) tu, vu P EpGq and (ii) u and v are oriented
toward each other. For each pair tu, vu, reverse the orientation of any one of tu, vu. For each vertex v P V3 ,
let u be any neighbor of v such that u P V1 , and re-orient v to the orientation of u.
Computing an `-orientation. For each positive integer k, we recursively define a DetLOCAL Op1q-round
algorithm Ak which computes a k-orientation. In what follows, we assume k ě 3 and |V pGq| ě k.
The algorithm Ak is described as follows. First, execute Ark{2s to obtain a rk{2s-orientation of G. With
respect to this orientation of G, define the following terminologies. Let P be the set of all maximal-size
connected subgraphs in G such that all constituent vertices are oriented to the same direction. Notice that
if P contains a cycle, then P “ tGu. Otherwise P contains only paths. Define P1 as the subset of P such
that P P P1 if and only if the number of vertices in P is at least k. Define P2 as the subset of PzP1 such
that P P P2 if and only if there exists another path P 1 P PzP1 meeting the following condition. There
exist an endpoint u of P and an endpoint v of P 1 such that tu, vu P EpGq, and u and v are oriented toward
each other. Define P3 “ PzpP1 Y P2 q. Observe that each P P P3 is adjacent to a path in P1 .
The paths in P2 are partitioned into unordered pairs such that P, P 1 P P2 are paired-up if and only if
there exist an endpoint u of P and an endpoint v of P 1 such that tu, vu P EpGq, and u and v are oriented
toward each other. For each pair tP, P 1 u, reverse the orientation of all the vertices in any one of tP, P 1 u. For
each path P P P3 , let P 1 P P1 be any path adjacent to P , and re-orient P to the orientation of P 1 .
The round complexity of Ak satisfies the recurrence T pkq “ T prk{2sq ` Opkq, which is Opkq.
?
?
Notice that if the p n ˆ nq-torus is oriented (i.e., the input port-numberings all agree with a fixed
N/S/E/W orientation [5]), then there is no non-trivial LCL problem solvable in Op1q time.

21 Even though orienting all vertices in the cycle to the same direction gives a legal labeling, `-orientation is still a non-trivial
LCL problem. Consider a subpath pv1 , v2 , v3 , v4 q in the cycle. Suppose that the port-number of pv2 , v3 q stored at v2 is 1, but
the port-number of pv3 , v4 q stored at v3 is 2. Then we need to label v2 and v3 differently (1 and 2, respectively) in order to
orient them in the same direction ‘Ñ’.

30

