arXiv CSopen access

The Distributed Complexity Landscape on Trees Depends on the Knowledge About the Network Size

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

cloud distributed-computing parallel-computing

distributed computing, parallel computing, cloud

The Distributed Complexity Landscape on Trees Depends on the Knowledge About the Network Size Alkida Balliu1 , Sebastian Brandt2 , Fabian Kuhn3 , Dennis Olivetti1 , Timothé Picavet4 , Gustav Schmid3

arXiv:2605.12787v1 [cs.DC] 12 May 2026

Gran Sasso Science Institute, L’Aquila, Italy CISPA Helmholtz Center for Information Security, Saarbrücken, Germany 3 University of Freiburg, Germany 4 LaBRI, Université de Bordeaux, France

Abstract One of the most successful theoretical models in distributed computing is the LOCAL one, introduced in a seminal work by Linial [SIAM J. Comp. 1992]. Over the years, when studying distributed graph problems in the LOCAL model, researchers made different assumptions on the exact details of this model. For example, sometimes it is assumed that all machines know the exact size of the network, other times machines are assumed to only know a polynomial upper bound on the size of the network, while sometimes no prior knowledge is assumed. Are these small differences irrelevant details or do they actually heavily affect the obtained results? We investigate how robust our current understanding of the LOCAL model truly is, by focusing on one of the most studied classes of problems, called Locally Checkable Labelings (LCLs). LCLs are graph problems for which correct solutions can be described by listing a finite set of valid constant-radius neighborhoods. Since Naor and Stockmeyer introduced LCLs [FOCS 1995], understanding them has been in the center of attention, and, in the last 10 years, researchers were able to make a lot of progress. For example, Chang, Kopelowitz, and Pettie [FOCS 2016] showed that the √ randomized complexity of any LCL problem on n-node graphs is at least its deterministic complexity on log n-node graphs. Later, Chang and Pettie [FOCS 2017], showed that, on bounded-degree trees, any randomized algorithm solving an LCL in no(1) rounds can be automatically transformed into a deterministic algorithm with runtime O(log n). Then, Balliu, Hirvonen, Korhonen, Lempiäinen, Olivetti, and Suomela [STOC 2018] showed that these kind of automatic speedups are no longer possible for general boundeddegree graphs. The above-mentioned results make use of the assumption that the nodes have, for free, prior knowledge of n. How much does this assumption affect the beautiful theory of LCLs as we know it nowadays? It turns out that, perhaps surprisingly, if we were to consider a setting where nodes are oblivious of n, or if we relax the setting such that nodes know a polynomial upper bound of n, already on trees, the theory of LCLs looks quite different from the one we currently know. In fact, while the fundamental classification of problems seems to remain the same, our results show that the picture becomes much more complex: for example, there are more cases in which randomness helps in solving LCLs faster; there are problems with very unnatural complexities; and for some problems the exact lower bound even depends on which definition of Ω we use!

Contents 1 Introduction 1.1 Some Useful Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 High-level Ideas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 3 5 8

2 Preliminaries 12 2.1 The LOCAL Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2 LCL Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3 k-hierarchical 2 12 -coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.4 Tree Decompositions and Complexity Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.5 Background for the Unusual Complexities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5.1 Different Definitions of Ω . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5.2 Taking Half a Logarithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3 LOCAL Without Extra Knowledge

4 Polynomial Upper Bound N Given 21 4.1 The Decomposition Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.2 The Optimization Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5 Lower Bound for the Case in Which a Polynomial Upper Bound on n is Given 26 5.1 An Algorithm That Requires O(n1/k ) Rounds for Infinitely Many Values of n . . . . . . . . . 27 5.2 Lower Bound for k-Hierarchical 2 21 -coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.3 Lower Bound for k-Rake-and-Compress Decomposition . . . . . . . . . . . . . . . . . . . . . . 31 6 Only Bounded IDs 32 6.1 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 6.2 Analyzing the Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 7 Randomized LOCAL Model 42 7.1 Upper Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 7.2 Lower Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 7.3 3-hierarchical 2 12 -coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

Introduction

Over the last 40 years, researchers have made remarkable progress in advancing our knowledge in the field of theoretical distributed computation. In the process of exploring such a vast area of research, it is only natural to study various meaningful models of distributed computing, each focusing on different aspects. One of the most successful theoretical models in distributed computing is the LOCAL one, introduced in a seminal work by Linial [32]. This is a synchronous message passing model, where a network is modeled as a graph, in which nodes represent machines, and edges represent communication links. When striving to understand the unknown, it helps significantly to simplify the context or, sometimes, the task at hand. For instance, when trying to design fast algorithms for distributed graph problems in the LOCAL model, it is very often assumed that the nodes of the graph are given, for free, prior knowledge of the total number n of nodes in the graph. In fact, in the literature, some algorithms are designed to work when the exact value of n is known a priori, others require to know only a polynomial approximation of n, while still for others this global knowledge of n is not needed at all. Assuming prior knowledge of the total number n of nodes is indeed quite useful: it allows us to design distributed algorithms that state operations like “first, each node v checks whether some property is satisfied in its O(log2 n)-radius neighborhood, then ...”. Such an operation requires that the algorithm is given a polynomial upper bound on n. However, while in the centralized setting knowing the size of the input is a natural assumption, in the distributed setting this is not quite realistic: think, e.g., of networks that change over time, or huge networks that span the whole world. Moreover, for many interesting distributed graph problems, learning the total number of nodes in a graph potentially requires much more time than solving the problem with the best known algorithm that receives this knowledge for free. Therefore, it is natural to ask the following questions. What can be solved efficiently, in the distributed setting, with algorithms that are not given as input the value of n or if nodes are only given an imprecise estimate of n? Are current algorithms heavily relying on the knowledge of n, and if they are, can we turn them into algorithms that do not have access to this information while maintaining the same runtime? How much would our knowledge change in a setting in which an algorithm is not given any prior knowledge of global parameters? Ultimately, how robust is our current knowledge in the theory of distributed computing? Some algorithms can be turned into uniform ones. The question of whether we can obtain uniform algorithms [31], that is algorithms which are oblivious to global parameters, has already been discussed in a few cases. In some cases, researchers have made an effort and asked whether the algorithms they were presenting could be made uniform. For example, in [18], Barenboim and Elkin first gave an algorithm for solving MIS when knowing n, and then, by paying some overhead on the runtime, they show how to turn their algorithm into one in which no knowledge about n is necessary. Moreover, there are some generic approaches that one could try for obtaining uniform algorithms. For instance, one could try to guess the value n of the total number of nodes: one can first run a non-uniform algorithm with some value N = N0 , then, if it fails, one can try again with some larger N , until one succeeds. By how much one increases the guess depends on the runtime of the given algorithm. Korman, Sereni, and Viennot refined this idea and designed a technique that proved useful for making existing algorithms uniform [31]. On a high level, their technique works as follows. They first run the algorithm with a guessed value of n: after this, some nodes are going to succeed, while some others are going to fail (think of the (∆ + 1)-vertex coloring problem; nodes that fail have got a color that conflicts with some neighbor). The nodes that succeed keep their output (their color), while the others run the algorithm with a suitably increased guess of n. The authors used this technique on many existing algorithms that solve variants of maximal independent set and vertex/edge colorings, obtaining uniform algorithms that asymptotically have the same runtime as the non-uniform ones. However, this technique can be applied only to a specific kind of algorithms. In fact, in order to be able to apply it, the algorithm must be able to provide an output that is compatible with the outputs of nodes that have already terminated. Parts of the distributed theory inherently can’t be made uniform. Despite the efforts of understanding distributed computing in the uniform setting, that is in the setting where algorithms may not leverage global parameters, many important results in the literature strongly rely on prior knowledge of global parameters, and previous techniques do not help in obtaining uniform and efficient algorithms. One 1

striking example is the successful line of research that studies Locally Checkable Labeling (LCL) problems. The research community put a lot of effort into understanding LCLs and yet a major part of the theory that researchers have built crumbles in an oblivious-to-n setting. In this paper, we make a first step forward in understanding this extensively-studied class of problems in the uniform setting and in settings where the knowledge about n is less accurate. Perhaps surprisingly, our results show that even when restricted to bounded-degree trees, when n is not known a priori, the theory of LCLs looks vastly different than the one we have known so far, and it gets more complex as well. LCLs were introduced in 1995 in the seminal work of Naor and Stockmeyer [35], and, informally, they are a class of problems for which correct solutions can be specified by listing a finite set of valid labeled constant-radius neighborhoods (plus some additional restrictions). Observe that this definition implies that the correctness of a solution for an LCL problem can be checked, distributedly, in constant communication rounds. Many well-studied problems fall into this class: maximal matching, maximal independent set, vertex coloring, etc. Since its introduction, the LCL class of problems has been extensively studied over the years (see e.g., [2–5, 12–17, 21, 23, 25–27, 29]), and one very well-studied aspect is the complexity landscape of LCLs: what are possible complexities of √LCLs? For example, nowadays we know that there cannot be any LCL with deterministic complexity Θ( log n). Moreover, it is worth mentioning that investigating LCLs has given insights and has helped in understanding problems outside the LCL class. For example, while LCLs are problems defined on graphs of bounded degree, the round elimination technique, which has been developed to understand the complexity of LCLs [20], has then been used successfully to show many different lower bounds in the unbounded-degree setting [6–9, 11, 22]. An interesting graph class where LCLs have been studied is trees. The graph class of trees is very important, not only because it is well-studied and natural, but also because, in the distributed setting, for many interesting natural problems, trees appear to be hard instances. For example, most lower bounds proved via the round elimination technique hold already on trees. Nowadays, the general feeling is that we know everything regarding the landscape of the deterministic and randomized complexities of LCLs on trees. In fact, we know that the deterministic complexity of any LCL problem on trees is one of the following: O(1), Θ(log∗ n), Θ(log n), or Θ(n1/k ) for all integers k > 0 [26]. The complexity gaps are constructive: if we design an algorithm that solves an LCL on trees in e.g., O(log2 n) rounds, then we can automatically speed it up and reduce its complexity to O(log n). We also know that randomness may only help for problems with deterministic complexity Θ(log n), and if it does help, it helps exponentially [25]. The case of trees already highlights a big issue suffered by the beautiful distributed complexity theory of LCLs that has been built over the years. For the so called lower regime O(log n) much is already known, while for the polynomial regime complexities Θ(n1/k ) the picture is unclear. LCLs that have complexity O(log n) when n is known to the algorithm, can be solved with normal-form algorithms that do not require any knowledge of n [25, 26]. See also the work of Brandt et al. [19], in which randomized uniform algorithms for LCLs in regular trees are considered. In that work, they consider algorithms such that for any ε > 0 they have the guarantee that any node running for at least T (ε) rounds has terminated with probability at least 1 − ε. They show the following equivalences between the standard randomized non-uniform LOCAL complexities and the uniform LOCAL complexities: O(1) = O(1), Θ(log∗ n) = Θ(log∗ 1/ε), Θ(log log n) = Θ(log log 1/ε) (where we should think of ε = n1c ). It seems reasonable to hope that similar results can be proven about the polynomial regime complexities Θ(n1/k ), but it is unclear upon closer inspection. In fact, all upper bounds of O(n1/k ) are shown by assuming that some value N = Θ(n) is given to the nodes and the algorithms heavily rely on this. If we instead give some value N = ω(n) to the nodes, then the upper bounds get asymptotically worse, and it is not known whether a tight Θ(n1/k ) complexity (for all integers k > 1) can be achieved without relying on such knowledge. In other words, some known facts about the distributed complexity theory of LCLs may collapse, and hence the following questions arise naturally. When relaxing the assumption that nodes have knowledge about the network size: Is it really true that randomness may help only for problems with deterministic complexity Θ(log n)? Is it really true that there are no LCLs with deterministic complexity in the range √ ω( n) to o(n)? How robust is our current knowledge of LCLs? In this work, we try to bring some clarity to these issues.

Figure 1: The lower bound instance for k-hierarchical 2 21 -coloring, for k = 3. Level-3 nodes are purple and form a path at the top. To each level-3 node, we attach a path of red level-2 nodes, and to each level-2 node we attach a path of yellow level-1 nodes. All paths have length Θ(n1/3 ).

1.1

Some Useful Background

In a cornerstone work, Chang and Pettie [26] proved that, on trees, there can be no LCL with a complexity that is in the range ω(log n) ∩ no(1) . After that, the techniques used in [26] have been used to prove many other different complexity gaps [14, 23]. In essence, in the ω(log n) region, there can only be problems with complexity Θ(n1/k ), for all integers k > 0, and, as shown in [23, 26]. We consider two natural examples of problems with such complexities: k-hierarchical 2 12 -coloring and k-rake-and-compress decomposition. The latter one of these problems is the theoretically more interesting problem since it is complete for the class of problems solvable in Θ(n1/k ) rounds. That is, if we have a fast algorithm for k-rake-and-compress decomposition, we can also solve any other LCL with complexity O(n1/k ) in the same asymptotic time [14, 23]. However, in the spirit of both brevity and presenting our ideas in a more understandable manner, we restrict our more involved proofs to the easier to deal with problem of k-hierarchical 2 12 -coloring. We note that k-hierarchical 2 12 -coloring is a natural candidate, since (1) it was the first family of problems revealing the Θ(n1/k ) classes, and (2) its study eventually lead to the classification of LCLs into these classes. Hierarchical coloring. The problem of k-hierarchical 2 12 -coloring requires us to produce a proper 2coloring, but only on some parts of a tree. We note that this is an artificial problem and its description may sound a bit convoluted. We explain the problem using the canonical lower bound instance shown in Figure 1. The graph is organized into hierarchical levels obtained by iteratively removing nodes of degree at most 2. Formally, level 1 consists of all nodes of degree at most 2 (shown in yellow). After removing these nodes, level 2 consists of all remaining nodes of degree at most 2 (shown in red). More generally, level i consists of the nodes that have degree at most 2 after removing all nodes of levels < i. The parameter k specifies the number of relevant levels; nodes of level larger than k may output arbitrary labels. Since k is a constant, membership in levels ≤ k can be determined within a constant-radius neighborhood. Each level induces a collection of pairwise disjoint paths. In the construction of Figure 1, with the particular case of k = 3, all such paths have length Θ(n1/3 ). Each level 1 path must either be properly 2-colored, or its nodes must unanimously be labeled decline. If the nodes of a level 1 path output a 2-coloring, then any adjacent level 2 node (at the two endpoints of the path) may output the label exempt. The exempt label is compatible with any other label, effectively removing all constraints and thus splitting a level 2 path into two independent subpaths. Level 2 paths (after splitting at exempt nodes) face the same choice: they must either produce a proper 2-coloring or unanimously output decline. This process continues up the hierarchy. At the final level k (level 3 in Figure 1), nodes are not allowed to output decline, and therefore every level 3 path, excluding exempt level 3 nodes, must be properly 2-colored.

• Lower bound intuition (case k = 3): In the instance of Figure 1, all level 1 paths have length Θ(n1/3 ). Producing a proper 2-coloring of such a path requires Ω(n1/3 ) rounds. Hence, if any level 1 path outputs a 2-coloring, the desired lower bound already follows. Otherwise, all level 1 paths output decline, and thus no level 2 node may output exempt. They therefore remain of length Θ(n1/3 ). So, the same argument applies here: if any level 2 path is 2-colored, this requires Ω(n1/3 ) rounds. If both level 1 and level 2 paths output decline, then the responsibility is pushed to level 3, where again no node is allowed to output exempt. However, level 3 nodes are not allowed to output decline, and thus must 2-color their path, which again has length Θ(n1/3 ). Consequently, in all cases, some path of length Θ(n1/3 ) must be 2-colored, implying an Ω(n1/3 ) lower bound. • Algorithmic idea: A matching upper bound of O(n1/3 ) rounds is obtained as follows. Each node explores the path it belongs to up to distance O(n1/3 ). If the path has length at most O(n1/3 ), the nodes produce a proper 2-coloring. Otherwise, the entire path outputs decline. At higher levels, nodes adjacent to already colored lower-level paths may output exempt, thereby splitting longer paths into smaller ones. Nodes that cannot output exempt must have attached a lower level path that outputs decline, such a declined path must have length Ω(n1/3 ) and so, by a charging argument, there can be at most O(n1−1/3 ) level-2 nodes that do not output exempt. Repeating this idea and exploring the level-2 paths until length O(n1/3 ), we ensure that the number of level-3 nodes that do not output exempt is at most O(n2/3−1/3 ) = O(n1/3 ). We then produce a proper two coloring of all level-3 paths in O(n1/3 ) rounds. • Role of knowledge of n: The algorithm requires nodes to know (an upper bound on) n in order to determine when to stop exploring their path. If a node stops too early, too few nodes will output exempt, leaving a long path at the final level. If it explores for too long, the runtime may exceed the O(n1/k ) bound. Rake-and-compress decomposition. While [26] gave k-hierarchical 2 21 -coloring as a first example of problems with complexity Θ(n1/k ) in trees, in [23] it has been shown that, for each integer k, there is a problem that is complete for the class of problems that can be solved in time Θ(n1/k ). That is, any Θ(n1/k )round problem can be solved by using an algorithm for the so-called k-rake-and-compress decomposition.1 Informally, a rake operation is the process of removing all nodes of degree exactly 1 and a compress operation is the process of removing all nodes of degree exactly 2. The goal is to repeatedly use these two operations to remove the entire graph, while using the compress operation only k − 1 times. More formally, we are required to partition the nodes of a given tree T into 2k − 1 subsets R1 , C1 , . . ., Rk−1 , Ck−1 , Rk , where the sets R1 , R2 , . . . are called rake layers and the sets C1 , C2 , . . . are called compress layers. The components of each rake layer have an edge orientation that forms a rooted tree, and the nodes of each compress layer form disjoint paths, whose endpoints again have a single outgoing edge towards a Rake node. Note that performing multiple rake operations in a row naturally leads to the removed nodes forming a rooted tree. Similarly a compress operation makes disjoint paths and the endpoints of the removed paths had only one neighbor that was not removed. So this problem is supposed to capture the process of repeatedly using these two operations to remove the entire graph. It is shown, in [23], that once such a decomposition has been computed, any LCL of complexity Θ(n1/k ) can be solved in a time proportional to the diameter of the largest connected component induced by nodes belonging to the same Ri layer. Moreover, by performing O(n1/k ) rakes (which produces the rake layer R1 ) followed by 1 compress (which produces the compress layer C1 ) and repeating this process k times (without performing the k-th compress), it is possible to compute a decomposition where the diameter of the largest connected component of every Ri is upper bounded by O(n1/k ) [23]. The formal definition of this problem is given in Section 2.4. The known algorithms for computing such decompositions have the same issues suffered by the known algorithms for k-hierarchical 2 12 -coloring: they strictly rely on having prior knowledge of n. 1 Note that the k in the names of both problems will be the same k as in the complexities, that is 2-hierarchical 2 1 -coloring 2 √ has complexity Θ( n) and computing a 3-rake-and-compress decomposition has complexity Θ(n1/3 ).

Why we restrict to these problem families. In our work, we prove lower and upper bounds for these families of problems, and show that minimal changes on the assumptions that are usually made in the LOCAL model can drastically affect the complexity of these problems. As k-rake-and-compress is a complete problem for LCLs of complexity Θ(n1/k ), we believe that all LCL problems of this class behave similarly. In order to avoid a long and technical analysis, we decide to only work on k rake-and-compress decompositions and the hierarchical coloring problems. Generalizing our theorems would significantly obfuscate the interesting aspects of our lower bound and upper bound results, specifically, how we optimize in these new settings and the concepts behind lower bounds in these new settings. Many possible assumptions. The assumptions made over the years when studying graph problems in the LOCAL model and similar models are many and of different flavors2 . For example, the above-described algorithms need to know a linear upper bound on n, and if we relax this requirement a bit by providing a polynomial upper bound on n, the complexity of these algorithms would get worse. However, some other algorithms in the literature work perfectly fine when given a polynomial upper bound on n, and others do not need to know n at all. Moreover, there are other types of assumptions made in the literature, that are not about the knowledge of n. For example, it is typically assumed that nodes are assigned unique IDs, and some algorithms rely on the fact that the range of possible IDs is small (e.g., polynomial in the number of nodes). Moreover, some algorithms assume and rely on the fact that all nodes know the range of the possible IDs, while some algorithms work fine even without this knowledge.

1.2

Our Contributions

In the following, we summarize our results. As we will show, not only is the complexity landscape of LCLs much more diverse than what was previously known, but also, the complexities even depend on which definition of Ω we use! No assumptions at all. We start our investigation in the most restrictive version of the LOCAL model: nodes do not have access to randomness and are not given any prior knowledge about n. To avoid trivial impossibility results, we assume that each node is assigned a unique ID that can be an arbitrary natural number. In fact, without IDs, even in a graph of just two nodes connected by an edge, it is impossible to solve basic problems like 2-coloring because the nodes are not able to break symmetry. In Section 3, we first illustrate the difficulties that we face in this model by giving an Ω(n) lower bound for k-hierarchical 2 21 -coloring, for any integer k. Theorem 1. For all integers k > 0, k-hierarchical 2 12 -coloring requires Ω(n) rounds, in the LOCAL model, where no bound on n, nor on the size of the ID space, is provided to the nodes. Then, in Theorem 2, we show that this lower bound also holds for computing k-rake-and-compress decompositions, which is the key component at the heart of the theory of LCLs in trees. Theorem 2. For all integers k > 0, solving k-rake-and-compress requires Ω(n) rounds, in the LOCAL model, where no bound on n, nor on the size of the ID space, is provided to the nodes. These results convey the following message. Having no knowledge at all about the size of the network, and no guarantees on the ID space, makes all the polynomial classes collapse. Hence, in order to find any non-trivial solution to these problems, some additional guarantees are required. 2 For instance, the dynamic-LOCAL model [1] is defined such that the algorithm knows the value of n.

If we define the dynamic-LOCAL model in perhaps the most intuitive way, where there is no assumption on the future number of nodes, the algorithms and known results do not follow through. However, the algorithms that we present in this paper would directly work in this version of dynamic-LOCAL. This shows that, when studying a model of computation, these assumptions really matter, even outside the standard LOCAL model.

Polynomial upper bound on n given. As a next step, we investigate the commonly considered setting in which nodes are provided a polynomial upper bound on n. More formally, we consider the setting in which nodes are given two inputs N and c, and are promised that n ≤ N ≤ nc . On a high level, we show that, problems that have complexity Θ(n1/k ) when n is known, still have a polynomial complexity in this setting, but the exponent of this polynomial depends in a complicated way on c and k. For this setting, we will provide upper bounds on the complexity of computing k-rake-and-compress decompositions in Section 4.1. We will show that the complexities of the algorithms that we provide can be derived by solving a non-trivial optimization problem. This will result in highly unnatural complexities. For √ 7− 13 example, for k = 3 and c = 3, we will obtain an algorithm with complexity O(n 6 ) ≈ O(n0.566 ) (which should be compared with the complexity O(n1/3 ) when n is known). Since computing such a decomposition is a complete problem for problems with complexity O(n1/k ) in the standard setting, we obtain the result stated in Theorem 3. 1

Theorem 3. Let Π be an LCL problem that, on trees, can be solved in O(n k ) rounds in the LOCAL model, when nodes are provided with a linear upper bound on n and IDs are from some polynomial range. Consider the LOCAL model where nodes are provided N and c, such that N is guaranteed to satisfy n ≤ k−i0 k j 1 1 . i α , where i := N ≤ nc . Let α1 < 1c be the unique real solution to the equation 1 = 1−cα 0 1 0 cα 1 1 The LCL problem Π can be solved in O(ncα1 + log∗ I) rounds on trees, where I is the largest ID assigned to any node. In Section 5, we will prove a matching lower bound. However, we will show that the actual complexities of these problems depend on which definition of Ω we use. In fact, there exist two incompatible definitions of Ω: the one by Hardy-Littlewood and the one by Knuth. We recommend Knuths original article [30] as a reference on the different notations. In the Hardy-Littlewood version, f (n) ∈ Ω(g(n)) states that there is a constant c > 0 such that f (n) ≥ c · g(n) for infinitely many, large enough, n. On the other hand, Knuth’s version is stronger and states that there is a constant c > 0, such that after some starting point n0 , we have f (n) ≥ c · g(n) for all n ≥ n0 . Our lower bounds use the weaker Hardy-Littlewood definition of Ω. We will show in Section 5.2 and Section 5.3 that the upper bounds that we provide for k-hierarchical 2 12 -coloring and for k-rake-and-compress decomposition are tight3 . More precisely, we prove Theorem 4 and Theorem 5. Theorem 4. Consider the LOCAL model where nodes are provided N and c, such that N is guaranteed to satisfy n ≤ N ≤ nc , and nodes are assigned unique IDs in {1, . . . , nc }. Let α1 < 1c be the unique value k−i0 j k 1 satisfying 1 = 1−cα i0 α1 , where i0 := cα1 1 . 1 Then, for the Hardy-Littlewood definition of Ω, the k-hierarchical 2 12 -coloring problem requires Ω(ncα1 ) deterministic rounds. Theorem 5. Consider the LOCAL model where nodes are provided N and c, such that N is guaranteed to satisfy n ≤ N ≤ nc , and nodes are assigned unique IDs in {1, . . . , nc }. Let α1 < 1c be the unique value k−i0 j k 1 1 satisfying 1 = 1−cα i α , where i := . 0 1 0 cα 1 1 Then, for the Hardy-Littlewood’s definition of Ω, the k-rake-and-compress decomposition problem requires Ω(ncα1 ) deterministic rounds. While it is a bit unsatisfying to use this weaker notion of Ω, it is in fact unavoidable. For the more commonly used definition of Ω due to Knuth, we will show, in Section 5.1, that proving ω(n1/k ) lower bounds is not possible. For this purpose, we design an algorithm that, for infinitely many values of n, is able to solve these problems in O(n1/k ) rounds. More precisely, we prove the following. 1

Theorem 6. Let Π be an LCL problem that, on trees, has complexity Θ(n k ) in the LOCAL model, when nodes are provided with a linear upper bound on n and IDs are from some polynomial range. Consider the LOCAL model where nodes are provided N and c, such that N is guaranteed to satisfy n ≤ 3 Technically there is still a log∗ (I) term in Theorem 3, but this is negligible as long as the largest ID I 2 something like 22

is bounded by

N ≤ nc . Then, for Knuth’s definition of Ω, the problem Π is not solvable in Ω(T + log∗ I) rounds, for any T that is asymptotically strictly larger than n1/k , where I is the largest ID assigned to any node. Our results for this setting can be summarized as follows. By slightly changing the usual assumptions, that is, by assuming that nodes know a polynomial upper bound on n, rather than a linear upper bound on n, we obtain that LCL problems now exhibit very different complexities. However, the added complexity can be dealt with in a structured and constructive way. Promise on the ID space. In Section 6, we consider the setting in which nodes are not given any upper bound N on n, but they are only given a parameter c, and are promised that the largest ID assigned to the nodes of the graph is at most nc . Observe that, while before nodes where given N and c, in this case nodes are given just c. Perhaps surprisingly, we show that for some problems this knowledge is sufficient. To be more precise, for k-hierarchical 2 12 -coloring, we are able to obtain an algorithm that matches the lower bound (for the stronger setting in which N is given) that we presented in Theorem 4. Note that while the bounds of Theorems 4 and 5 work for all LCLs, we present here an algorithm only for 2 12 -coloring, since the technical details are already complicated enough for this problem. Theorem 7. Consider the LOCAL model where nodes have no knowledge of n, but are assigned unique IDs k−i0 1 in {1, . . . , nc }, and c is known by all nodes. Let α1 < 1c be the unique value satisfying 1 = 1−cα i0 α1 , 1 j k 1 1 cα1 where i0 := cα1 . Then, for all k > 1, k-hierarchical 2 2 -coloring can be solved in O(n ) deterministic rounds. This implies the following exciting possibility. A promise on the size of the ID space may be just as good as having an actual upper bound on the number of nodes. Randomized algorithms. The final setting examined in this work is the randomized setting, where nodes do not have any knowledge about n (see Section 7). In the randomized LOCAL model, nodes are given access to an arbitrary number of random bits and they typically do not have access to unique IDs. If each node knows a polynomial upper bound on the number of nodes, the nodes can use the randomness to generate unique O(log n)-bit identifiers w.h.p. Even without any knowledge about n, the nodes can still use the randomness to generate unique (infinitely long) names, thus we consider nodes receive no additional input (in particular no form of IDs). In the version of the randomized LOCAL model where a linear bound on n is known, randomization does not help at all when solving the problem of k-hierarchical 2 12 -coloring [23]. However, in the setting without any bound on n, randomness actually provides an advantage over the corresponding deterministic case (the case of Theorem 1). We first show that the complexity of computing a 2-hierarchical 2 12 -coloring in the oblivious-to-n setting is Θ( logn n ), in contrast to the deterministic complexity Θ(n). We then go on to show that our ideas can be pushed further to the 3-hierarchical 2 12 -coloring problem, where we can observe some interesting behavior. We give an algorithm that solves 3-hierarchical 2 12 -coloring n in time O( f (n) ), where f (n) is a functional square root of log n. That means that f (n) is a function that satisfies f (f (n)) = log n. Note that f (n) is a function that grows much slower than any polynomial function, but also much faster than e.g., any polynomial in log n (cf. Section 2.5.2 for a more detailed discussion). We additionally prove that this is not just an artifact of our techniques, by also proving a lower bound of Ω f (n)nlog n , which makes the upper bound result nearly tight. We believe that this suffices to illustrate the possibly unexpected behavior that is emerging in this setting and we leave the full generalization as a 7

open question for future research4 . Our results about 2 and 3-hierarchical 2 12 -coloring are formally stated and proven in Theorems 58, 59, 61 and 62. In the standard LOCAL model, it is known that randomness helps on trees only for LCLs with deterministic complexity Θ(log n). Our results imply that this statement is an artifact of the assumptions that are typically made. In more restricted settings, randomness can be used in non-trivial ways to get faster algorithms. Open questions. While our work implies many new open questions regarding the complexity of graph problems when we deviate from common assumptions, we highlight the following two open questions which are most related to this work. • Let Π be an arbitrary LCL problem which, when n is known, has complexity Θ(n1/k ). What is the complexity of Π in the setting in which an upper bound N ≤ nc on n is given, and c is known by all nodes? What about the setting in which IDs are bounded by nc and c is known? • Let Π be an arbitrary LCL problem which, when n is known, has complexity Θ(n1/k ). What is its randomized complexity if n is not known? Note that, in our work, we answer these questions only for the problems of k-hierarchical 2 21 -coloring and k-rake-and-compress decompositions, and in the randomized case, only for k = 1 and k = 2.

1.3

High-level Ideas

We describe the challenges and key ideas in each of the discussed settings. No assumptions at all. In this setting, where nodes do not have any knowledge about n and IDs are unbounded, we prove Ω(n) lower bounds. The key difficulty in this setting is that IDs carry no useful information. We illustrate the lower bound idea with the 2-hierarchical 2 12 -coloring problem. Imagine a node v located in the middle of a path with monotonically increasing IDs in both directions (see Figure 2 on the left). From v’s perspective, every additional round only reveals one more hop of the path. If the node keeps exploring the path for too many rounds, an adversary can choose n so that the explored portion is in fact the entire graph, implying that the algorithm already spent Ω(n) rounds. Hence, to achieve sublinear runtime, nodes must terminate after a bounded number of rounds, without seeing the full extent of the path. However, a node that has only seen a constant-radius neighborhood cannot safely produce a consistent 2-coloring of the path. Therefore, level 1 nodes must output Decline after a constant number of rounds. Since this decision is local, it propagates to all level 1 paths, which thus unanimously output Decline. But if we can force very short level-1 paths to decline, we can construct a hard instance by attaching many such level 1 paths to a long path of level 2 nodes (see Figure 2 on the right). As all adjacent level 1 paths output Decline, none of the level 2 nodes may output exempt, and must produce a consistent 2-coloring of the top path. Since this path has length Ω(n), this instance requires Ω(n) rounds to be solved. The lower bound for computing a k-rake-and-compress decomposition essentially follows the same idea, but the technical details are more involved. Polynomial upper bound on n given. In the setting where nodes are provided with a constant c and a polynomial upper bound N ≤ nc , the previous trade off of the oblivious setting above becomes manageable. For our upper bound, we adapt the original O(n1/k ) round k-rake-and-compress decomposition algorithm that is known to solve all LCLs [23]. That algorithm uses the two subroutines rake and compress. 4 Some back-of-the-envelope calculation suggest that the following generalization might be true. For k ≥ 2, the complexity n of the k-hierarchical 2 12 -coloring problem seems to be O f (n) , where f (·) is a function such that f (k−1) (n) = log n. That is, for k = 2, we have f (n) = log n, for k = 3, we have f (f (n)) = log n, for k = 4, we have f (f (f (n))) = log n, and so on.

Figure 2: We depict the impossible trade off that an algorithm is faced with when solving 2-hierarchical 2 12 -coloring in the oblivious setting. From the perspective of a level-1 node (on the left), the node can tell it is in a path, but it has no information of how long this path is compared to the remaining instance. If it is not willing to spend Θ(n) rounds, it will have to terminate in a constant number of rounds. But this results in the construction on the right, where all level-1 paths have constant length and decline too quickly, leaving a linear-in-n length level-2 path on top that must be 2-colored.

R1 Figure 3: An example of a rake-and-compress decomposition, obtained by applying, in order, 2 rake operations, a single compress operation, and 2 rake operations. The red and green rake layers R1 , R2 form rooted trees, while the (in this case single blue) compress layer C1 form disjoint paths. Notice that every edge incident to a rake vertex is oriented in accordance to the order induced by the layers. A rake operation is the removal5 of all degree ≤ 1 nodes and a compress operation is the removal of all nodes of degree exactly 2. A rake-and-compress decomposition is then obtained by repeatedly performing O(n1/k ) rakes, followed by a single compress (see Figure 3 for an example). It can be shown that only one application of this is 1 -fraction of all nodes. So, after repeating it k − 1 times, only O(n1/k ) nodes guaranteed to remove a n1/k remain. Those nodes can now be “raked away” with the final O(n1/k ) rake operations. The trivial way to extend this approach to the new setting is to just do O(N 1/k ) rakes followed by a compress, but this can be improved. Informally, the improvement over the O(N 1/k )-round adaptation of the original algorithm comes from parameterizing the phases of the algorithm (see Section 4.1). Instead of using the same budget N 1/k in each phase, we perform N αi rake steps in phase i, for carefully chosen exponents αi . There is a sweet spot in choosing the value of these exponents. To ensure a good runtime when N is 5 In this context, “remove” does not mean that the node physically disappears from the graph.

Rather, it means that the node is marked as processed (or assigned to the current layer of the decomposition), and the algorithm proceeds on the residual graph induced by unprocessed nodes.

close to nc , the αi ’s should be small. However, if N is large, even with a small α1 , we have performed so many rakes that we have already removed a large portion of the graph. Therefore, we can afford to increase the other αi , because if N is too large, we will already have removed the entire graph well before having performed N αi many rakes. This allows us to increase the αi across phases: if the algorithm does not terminate early, it implicitly indicates that N is closer to n, and we can afford to spend more rounds. Balancing these effects leads to an optimization problem that determines the optimal choice of the αi (see Section 4.2). Why we can’t use Knuths definition of Ω: Before talking about our lower bounds for the polynomial setting, we discuss here why we use the Hard-Littlewood definition of Ω for our lower bounds. As already mentioned above, it is, in fact, impossible to show a lower bound of ω(n1/k ) for this setting with a polynomial bound on n. To prove this, we give an algorithm that is slow for most values of n, but runs in O(n1/k ) for infinitely many values of n. On a high level, we are able to achieve such a result as follows. For any given N , we will fix a strategy to guess what the true n is. We then use this guess N ′ as if it were the actual n. This guess will be correct for infinitely many n (no matter which N is given as input, we will correctly guess n). Whenever we have guessed the correct n, our algorithm will run in time O(n1/k ), which is sufficient to violate Knuth’s definition of Ω. c We have the promise that all nodes in our graph are given the same upper bound n1/c≤ N ≤ n and all nodes know c. So, the nodes know that the true n must be somewhere in the range N , . . . , N . To guess the correct n, we define a sequence of values that are very far apart, so that for any given N , only one element of the sequence falls in the range N 1/c , . . . , N . For example, the recursive sequence defined below is one of them. s1 = 2, si+1 = s2c for i ≥ 1 i When n is itself an element si of the sequence, then no matter what N is given to the nodes, we will know si = n ∈ N 1/c , . . . , N . With this in mind, our guessing strategy is simply the following: if there exists an si ∈ N 1/c , . . . , N , then act as if the actual number of nodes in the graph is si . This guess will be correct whenever n = si , no matter which N is given as input. Hence, the algorithm will run in O(n1/k ) for all n ∈ {si }i . Lower bounds with a polynomial upper bound. The parameters αi in our upper bound are derived from an optimization problem that captures the trade-off described above: choosing the αi too large leads to excessive runtime when N is close to nc , while choosing them too small limits the progress made in early phases and does not make the remaining instance significantly easier. We then proceed to prove a lower bound of ncα1 . By showing a lower bound matching our upper bound, we show that this optimization problem perfectly represents this tradeoff: it exactly captures the difficulty of this setting. Let us think of the conceptually easier 2 12 -coloring problem. Remember that each node is assigned a level 1, . . . , k, where each level consists of disjoint paths. Conceptually, a level-i node v has at least one path of level-(i − 1) nodes attached to it, and if this attached path outputs a 2-coloring, then the constraints on v are removed and v may output exempt. If instead, all level i paths adjacent to v output the decline label, the constraints on v remain. This behavior represents the tradeoff for the problem of 2 12 -coloring; if all level-i paths that output the decline label have length at least L, then if there are ni nodes of level i in total, it follows that at most ni /L nodes of level i + 1 are still constrained. This means that the remaining instance is small and hence easier. The proof extends the idea from the setting without knowledge of N by playing a sort of adversarial game between the algorithm and the instance. There, we essentially asked the algorithm how long it is willing to explore a path of level-1 nodes until it commits to outputting a decline label on such a path. If it spends more than N α1 rounds, then, by setting N = nc , the algorithm runs for too long. If instead, the nodes decide to output decline when the path is much shorter than N α1 , the adversary sets N = n, which means the number of higher level nodes without properly 2-colored neighbors is very large. Then, even if 10

the perfect trade-offs are made for all higher levels, we still have a long path that eventually needs to be properly 2-colored. Carefully repeating this argument over k −1 phases enforces the same trade-off throughout the execution. As a result, if an algorithm deviates from the behavior described in the optimization problem, it necessarily has to 2-color a path that is too long at some point. Thus, despite its complex appearance, the optimization problem exactly captures the aforementioned trade-off, yielding tight lower bounds. Promise on the ID space. In our next result, we consider only a promise on the size of the largest ID instead of a promise on the concrete number of nodes. We have to deviate from the upper bound strategy described above, but we will still rely on the same tradeoff described by our optimization problem. Since the nodes do not have any estimate of n given as input, we instead have to rely on an indirect measure: the identifiers that they see. To this end, consider the node v in the left part of Figure 2. Node v will now decide to Decline in the following way. Let i be the current round number and let IDmax be the largest ID that node v has seen so far. Then v will output Decline if i > (IDmax )α1 , where α1 is the same constant as in the optimization problem. This will result in some nodes deciding to Decline very quickly. However, we are able to show that this is not the case for too many nodes. For this, we introduce Decline Gadgets. They are a small graph structure equipped with a node ID assignment, that make our algorithm output Decline on one of their nodes. What makes Decline Gadgets special is that they are a sort of necessary condition to force our algorithm to output Decline. That is, whenever a node in a real instance outputs Decline, it is precisely because such a gadget is present. Using the fact that the number of available IDs is limited, we can bound the maximum number of such gadgets. This allows us to prove that our algorithm makes sufficient progress and obtains the same runtime as the algorithm providing the polynomial upper bound. Randomized algorithms. We now focus on the randomized setting, where nodes are given unlimited random bits. The key idea here is that nodes can obtain a crude estimate of log n despite having no knowledge of n. Again, consider the setting in the left of Figure 2, where a level-1 node v sees only its own level-1 path and needs to figure out when to decide to output decline. We now apply the following strategy: Each node independently marks itself with probability 1/2. Nodes then explore their level-1 path until either the path ends, or a marked node is encountered. Upon seeing a marked node, they immediately output Decline. This simple mechanism induces a probabilistic length threshold. Any level-1 path of length Ω(log n) contains a marked node with high probability and therefore declines. Conversely, if a path does not encounter any marked node, then with high probability, its length is at most O(log n), thus giving the level-1 nodes some confidence to keep exploring their path. Therefore, randomization allows nodes to implicitly recover a notion of the log n scale without explicit knowledge of n. The consequences for the level-2 nodes are roughly as follows. A level-2 path only needs to be fully 2-colored if all its attached level-1 paths decline. If the level 2 path has at least polynomial in n length, then there must also be polynomially many level-1 paths that have all decided to decline. W.h.p., this only happens if a majority of all those level-1 paths are Ω(log n) nodes long. Thus, such a level-2 path can only have length at most O(n/ log n) w.h.p., which is why this is the complexity of our algorithm. For the lower bound, we observe that a node in the middle of a long level-1 path must decide to decline within constant time with at least constant probability (otherwise, we can force the algorithm to require Ω(n) rounds on some path graphs). Any level-1 path of length Θ(log n) therefore has to decline w.h.p. and we can thus create a level-2 path of length Θ(n/ log n) that has to be 2-colored. When generalizing to 3 levels, we treat level 1 exactly as before. If we encounter long level-2 paths whose attached level-1 paths all decline, we obtain coarse information about n: namely, such level-1 paths must have length Ω(log n). So when relating the lengths of these level-1 paths to the length of our level-2 paths, the question becomes: at what length should we decide to start declining level-2 paths as well? From a high-level perspective, this again leads to an optimization problem analogous to the deterministic case, where a polynomial bound on n was given.

However, the nature of this optimization problem changes significantly. In the polynomial setting, it suffices to optimize over functions of the form nα for small constants α. Here, in contrast, the information available is only at the scale of log n, and it is no longer clear that restricting attention to polynomial functions yields the correct trade-off. Instead, one must optimize over a much broader class of functions. In fact, solving the resulting optimization problem reveals that the correct threshold is given by a function f (n) satisfying: f (f (n)) = log n. n ). Thus, unlike in the polynomial regime, here the optimal This yields an algorithm with complexity O( f (n) choice is characterized implicitly over the whole space of functions via a functional equation, reflecting the fundamentally different scaling behavior in the randomized setting. Compared to the other settings, the lower bound is established using a similar, albeit significantly more technical argument. Still, we are able to show that our optimization problem is the correct one, by proving an almost tight lower bound of Ω( f (n)nlog n ).

Preliminaries

We rely on classical graph theoretical notation, and refer to an undirected graph as G = (V, E). In addition to edges, we also refer to halfedges, that is the set Ē := {(e, v) | e ∈ E ∧ v ∈ e} , which essentially splits every edge into two parts. For our formal definition of LCLs, we will require labelings of the halfedges ϕ : Ē → Σ, that assign every halfedge a label from some set Σ. We denote by Br (u) the radius r ball around a node u ∈ V , and sometimes we also refer to this as the r-hop neighborhood. Throughout this work, we will restrict ourselves to the setting where the maximum degree ∆ is a constant and where all graphs are trees.

2.1

The LOCAL Model

The LOCAL model is a model of distributed computing. This means that we are given a network represented as a graph G = (V, E), where each node represents a computational unit, and edges represent communication links. Nodes are assumed to be entities with unlimited computational power and communication links are unbounded in the amount of information they can transmit. Time is measured in synchronous rounds of communication. Nodes all start at the same time (round 0), then in each round any node can send an arbitrary amount of information (e.g. its entire state) to all of its direct neighbors and then perform arbitrary computation. At the end of the computation, each node must produce an output, such that all outputs together solve the computational task. For example, each node is required to output a color, and the solution is globally correct if there does not exist a monochromatic edge. Additionally, nodes may start the computation with some predetermined inputs in round 0. For example, if we restrict the nodes to only perform deterministic computation it is common to give each node a unique identifier from the set [1, nc ], for some constant c ≥ 1. This is then called the deterministic LOCAL model. Most often, nodes are also provided with knowledge about some of the graph parameters, like the number of nodes n and the maximum degree ∆. What exactly is given as an input to the nodes in round 0 varies between different works in the field. In Section 3 we assume that nodes are restricted to deterministic computation and are given unique natural numbers as IDs, nothing else, so in particular no upper bound on n is known. In Sections 4.1 and 5, we assume nodes are restricted to deterministic computation and are given two natural numbers N, c ≥ 1 as inputs, together with the promise that n ≤ N ≤ nc . Additionally, nodes are given a unique ID from the set [1, nc ]. In Section 6, we assume nodes are restricted to deterministic computation and are given only one natural number c ≥ 1 as input. Again nodes are given unique identifiers from the set [1, nc ]. In Section 7, nodes are given access to an unbounded number of random coins. Nodes are not given any additional information, so they know nothing about n and are not provided with any IDs. 12

2.2

LCL Problems

An LCL problem Π = (Σin , Σout , r, C) is a quadruple where • Σin is a finite set of input labels • Σout is a finite set of output labels • r ∈ N is the checkability radius of Π • C is a finite set of input-/output- labeled centered r-hop neighborhoods C ∈ C. The labeling assigns every halfedge in C an input label from Σin and an output label from Σout . A solution to Π on a Σin labeled graph (G, ϕin ) is an output labeling σout that assigns every halfedge in G an output label from Σout , such that for every node v, the input-/output- labeled r hop ball around v is isomorphic to a member of C. LCLs with labels on nodes. For our definition of the LCL k-hierarchical 2 12 -coloring, we will refer to labels on nodes instead. Note that we can encode labels on nodes, by using labels on edges, by requiring all halfedges adjacent to some node v to output the same label.

2.3

k-hierarchical 2 12 -coloring

Many of our results are about k-hierarchical 2 12 -coloring. These problems are the first example of problems with complexities Θ(n1/k ) [26]. From a high level view, k-hierarchical 2 12 -coloring exactly captures what makes a problem with complexity Θ(n1/k ) hard: we might have to solve a global problem in some long path. The value of k determines how much freedom we have in choosing which path to solve this hard problem in. The k-hierarchical 2 21 -coloring problem is defined in the following way. Given a tree G = (V, E), we define k sets L1 , . . . , Lk , called respectively level 1, . . . , k. We define the levels inductively on 1 ≤ i ≤ k. First, L1 = {v ∈ V | deg(v) ≤ 2}. S Let G(i) be the subgraph induced by V (i) = V \ 1≤j<i Lj . We then have Li = {v ∈ V (i) | degG(i) (v) ≤ 2}. We call G(k+1) the remainder. Each node is either in a level 1, . . . , k, or in the remainder. Which set a node v belongs to can be determined in k rounds. There are no input labels, and the set of output labels is {B, W, E, D}, which stand for Black, White, Exempt and Decline respectively. The constraints are as follows: 1. All nodes in the remainder output D. 2. No node in level k may output D and no node in level 1 may output E. 3. No node that outputs W can be adjacent to a node of the same level that outputs W , or D. Similarly no node that outputs B can be adjacent to a node of the same level that outputs B, or D. 4. A node may only output E, if it is adjacent to a lower level node that outputs one of {B, W, E}. This concludes the problem description. We make the following observations. • Each level consists only of isolated nodes and paths. • Each level-1 path is either properly 2-colored, using W, B, or all nodes output D. • Each level ≥ 1 path consists of continuous subpaths that are either properly 2-colored, or where all nodes output D. These subpaths must be separated by nodes that output E. 13

• If G(k) is non-empty, then at least one path must be properly 2-colored. If no level < k node outputs B, or W , then no node is allowed to ever output E. Importantly, no node of level k can output E. Since level k nodes cannot output D, they are forced to output a consistent 2-coloring. Essentially, the class of the 2 21 -coloring problems are considered the canonical representatives of the complexity classes Θ(n1/k ). They are first introduced in [26] as the first examples of LCLs that have the polynomial complexities Θ(n1/k ). As a result, all of these complexity classes are non-empty. Lemma 8 ([26]). For any k ∈ N, k-hierarchical 2 21 -coloring has complexity Θ(n1/k ).

2.4

Tree Decompositions and Complexity Classes

When restricting the input graph to a tree, the distributed complexities that exist for LCL problems are very well understood. This setting is therefore an excellent case study for our question of how giving different initial inputs to nodes changes the model. To this end we give an overview about which polynomial complexity classes exist on trees in the LOCAL model, when nodes know a linear upper bound on n. At the heart of the study of these complexity classes are rake-and-compress decompositions. Definition 9 ((γ, ℓ, L)-decomposition [26]). A (γ, ℓ, L)-decomposition of a tree T is a decomposition of the C consist of paths and the nodes in 2L − 1 rake and compress layers. The compress layers V1C , . . . , VL−1 R R R R R rake layers V1 , . . . , VL each consist of γ sublayers Vi = (Vi,1 , . . . , Vi,γ ). The layers satisfy the following R R R properties, based on the layer ordering ViR < ViC < Vi+1 and Vi,j < Vi,j+1 for all 1 ≤ i < L − 1, 1 ≤ j < γ. 1. The components of each compress layer ViC are isolated paths of length in [ℓ, 2ℓ]. Furthermore, the endpoints of each such path have exactly one neighbor in a higher layer. All other nodes have no neighbors in higher layers. R 2. The components of each rake sublayer Vi,j are isolated nodes with at most one neighbor of a higher layer.

With the decomposition formally defined, we can give formal descriptions of the two operations. Assume we already have a (partial) (γ, ℓ, L)-decomposition of some subtree T ⊂ G. Let the remaining graph be Ḡ = G \ T . The Rake Operation: Only nodes that have degree ≤ 1 in Ḡ participate in a rake operation. If there are two degree-1 nodes connected by an edge, only one of them participates, chosen arbitrarily. Any node v R R that participates computes the minimum Vi,j , such that Vi,j is larger than the layer of all of v’s neighbors R in T . Then v outputs Vi,j . Note that 1 ≤ i ≤ L and 1 ≤ j ≤ γ. Inside of a compress procedure we will need to compute a (ℓ, 2ℓ)-ruling set6 . To do this efficiently, we first precompute a distance-ℓ O(1)-coloring at the beginning of the algorithm. Since ∆ ∈ O(1) this can be done deterministically by using e.g. Linial’s coloring-reduction algorithm on Gℓ in O(log∗ C) rounds. Here, C is the size of some initial coloring, which is typically given by the initial unique IDs assignment. Given such a coloring we can compute a (ℓ, 2ℓ)-ruling set in O(1) rounds, by simply iterating through the colors. Having clarified this, we can describe the compress procedure. The Compress Operation: The compress operation takes as input two values ℓ ∈ N and 1 ≤ j ≤ L − 1. Let P be any maximal subpath of nodes of degree exactly 2 in Ḡ, of length at least ℓ. We first compute a R (ℓ, 2ℓ)-ruling set on P . Then all ruling set nodes join layer Vj+1,1 and all of the remaining nodes join layer VjC . Clearly a Rake operation can be performed in just one round of the LOCAL model. For ℓ ∈ O(1) and using the already discussed idea of precomputing a distance coloring, a Compress operation can be performed in O(1) rounds, after an initial O(log∗ IDmax ) rounds of precomputation. 6 An (a, b)-ruling set is a subset S of the nodes of the input graph such that the distance between any two nodes from S is

at least a and for each node u that is not contained in S, there is a node from S that is in distance at most b from u.

We then compute a (γ, ℓ, L)-decomposition, by performing γ rakes, followed by a Compress(ℓ, j) and then repeatng these two steps for 1 ≤ j ≤ L − 1. We then finish with another round of γ rakes. Doing this we get the following results. Lemma 10 ([26]). For ℓ ∈ O(1) and any positive integer k, set γ = n1/k (ℓ/2)1−1/k then a (γ, ℓ, k)decomposition can be computed in O(kn1/k ) rounds. Lemma 11 ([26]). For ℓ ∈ O(1) and γ ∈ O(1) then by setting L ∈ O(log n) a (γ, ℓ, L)-decomposition can be computed in O(log n) rounds. However, Lemma 10 assumes that nodes know a linear upper bound on the number of nodes. For Lemma 11 the only implicit assumption is that log∗ (IDmax ) ∈ O(log n), where IDmax denotes the largest ID. We will soon see that by varying these assumptions we significantly change the complexity of computing a (γ, ℓ, L)-decomposition. This is significant, because (γ, ℓ, k)-decompositions are in some sense Θ(n1/k )-complete. This immediately implies that the complexity landscape of LCLs significantly depends on these assumptions. The completeness of these decompositions comes from the following result. Lemma 12 ([23]). Let k be a positive integer. Assume a (γ, ℓ, k)-decomposition can be computed in Tdec . If an LCL Π admits an o(n1/(k−1) )-round algorithm, then Π can be solved in time Tdec + kγ. Together with this result from [26] we completely settle the types of polynomial complexities that exist in the LOCAL model, where a linear bound on n is given. Lemma 13 ([26]). Let k be a positive integer. Assume a (γ, ℓ, O(log n))-decomposition can be computed in Tdec . If an LCL Π admits an no(1) algorithm, then Π can be solved in time Tdec + γ log n. We get as a corollary. Corollary 14 ([24, 26]). Let Π be an LCL on trees in the LOCAL model, where nodes know a linear upper bound on n, then one of the following is true. • There exists a k ∈ N, such that Π has complexity Θ(n1/k ). • Π has complexity O(log n). Importantly, Corollary 14, does not guarantee that these complexity classes actually exist. However, the complexity of k-hierarchical 2 21 -coloring implies that such classes are non-empty. Given the importance of rake and compress decompositions, in our work we study the complexity of these problems. Unfortunately, the problem of computing a (γ, ℓ, k)-decomposition cannot be expressed as an LCL problem. For this reason, we introduce the k-rake-and-compress family of LCL problems, which requires us to compute a decomposition where the value of γ does not matter. This idea was first introduced in [10]. Definition 15 (k-rake-and-compress). For any integer k, the output of the k-rake-and-compress problem is a partial orientation of the edges and an assignment of one label out of Σout = {R1 , . . . , Rk , C1 , . . . , Ck−1 } to each node. The labels R1 , . . . , Rk are called rake labels and C1 , . . . , Ck−1 compress labels. Any legal labeling must satisfy the following rules, based on the ordering of the labels R1 < C1 < R2 < C2 < R3 < · · · < Ck−1 < Rk : 1. All edges adjacent to at least one node labeled rake must be oriented, while the other edges must not be oriented. 2. Each node v has at most one edge e = (v, u) oriented outgoing, except for compress nodes that have two compress neighbors. Such compress nodes must not have any outgoing edge. 3. For all oriented edges (u, v) the label of v is larger than or equal to the label of u. 4. For all compress labels, the subgraph induced by the nodes of that label consists only of disjoint paths. 5. Two nodes that have a different compress label must not be adjacent. 15

Note that any (γ, ℓ, k)-decomposition automatically also gives a solution to the k-rake-and-compress problem: simply have nodes output their respective rake or compress layer. However, the converse may not hold, since in a solution for k-rake-and-compress there is no bound on the diameter of the connected components induced by nodes belonging to the same rake layer. We now provide some intuition on the rules used to define k-rake-and-compress. • Because of items 1 and 2 all components of nodes that output rake labels are consistently oriented. • Because of items 4 and 5 compress labels are only used in paths and two different compress paths are separated by at least one rake label. • Item 3 means that we have to keep track of the number of compresses that we have already performed. To handle long paths we will simply let the nodes output a compress label and then have both endpoints pick a strictly larger rake label. Then we orient the edges connecting the endpoints towards the endpoints. Clearly this works only if we still have an available compress label.

2.5

Background for the Unusual Complexities

In computer science, the most common definition of the set Ω(f (n)) is due to Knuth. However, there exists an alternative, but incompatible, definition due to Hardy and Littlewood. In Section 5 we prove a lower bound for the Hardy-Littlewood definition of Ω, diverging from common notation. Surprisingly, we prove that this deviation to a strictly weaker version of this lower bound is necessary. We have another case of unusual behavior that we encounter in this work. In Section 7, we prove tight upper and lower bounds for a complexity that involves a function f (n), such that f (f (n)) = log n. Essentially, this function is the functional square root of the logarithm. In other words, it is obtained by taking half a logarithm. 2.5.1

Different Definitions of Ω

Two different definitions of Ω exist in the literature. Let f : N → N and g : N → N be two functions. The first is the Hardy-Littlewood definition: f (n) ∈ Ω(g(n)) ⇐⇒ ∃k > 0, ∀n0 , ∃n > n0 , |f (n)| ≥ k · |g(n)|. The second is the Knuth definition: f (n) ∈ Ω(g(n)) ⇐⇒ ∃k > 0, ∃n0 , ∀n > n0 , |f (n)| ≥ k · |g(n)|. The Hardy-Littlewood version indicates that f is larger than g infinitely often. On the other hand, Knuth’s version is stronger and indicates that, after some starting point n0 , f is always bounded below by n g. For instance, for f (n) = n(−1) and g(n) = n, we have f (n) = Ω(g(n)) according to Hardy-Littlewood’s definition, but not according to Knuth’s definition. This difference will be key in some of our results, and we seem to have stumbled upon one of the rare cases where we cannot just rely on Knuth’s definition. Indeed, Theorem 6 proves that without using the Hardy-Littlewood definition, we cannot improve the lower bounds of any LCL with complexity Θ(n1/k ) in the standard LOCAL model. The only part in which the Hardy-Littlewood definition is used in this work is in Section 5, in which we are very explicit about what definition we use. In all other parts of this work, we use the Knuth’s definition. 2.5.2

Taking Half a Logarithm

In Section 7, where we study the randomized complexity of 2 12 -coloring in the case where nothing is known about n, the complexity of the 3-hierarchical 2 12 -coloring problem turns out to not be easily expressible by analytic functions or generally by functions that we usually use to analyze the complexity of algorithms. The complexity of 3-hierarchical 2 12 -coloring turns out to essentially be of the order n/f (n), where f (x) is a function for which f (f (x)) = ln x. Such a function f (x) is also known as a functional square root of log x [33]. The inverse function of f (x) is a so-called half-exponential function h(x) for which h(h(x)) = exp(x). It was 16

shown in [28], that there are infinitely many functions h(x) that satisfy this identify and that are strictly monotonically increasing, continuous and continuously differentiable. The same is therefore also true for functions f (x) satisfying f (f (x)) = ln x. In [33], it is shown that if f (x) is restricted to a family of functions that can be expressed by some specific power series, then f (x) is indeed unique. To the best of our knowledge such half-logarithmic and half-exponential functions have not been widely studied. They have however in particular appeared in the context of circuit complexity [34]. In the context of this paper, we assume for every a > 1 a half-logarithmic function fa (x) : R → R that satisfies fa (fa (x)) = loga (x) (for x ≥ a) and that has the following properties. • fa (x) is continuous and strictly monotonically increasing in x • For all 1 < a < b and all sufficiently large x, we have fb (x) < fa (x). Such a family of functions fa (x) might not be efficiently or explicitly constructible, but it definitely exists. Under those assumptions, we can show that fa (x) satisfies some useful additional properties. One can in particular show that for any fixed 1 < a < b, we have fa (x) = Θ(fb (x)). To see this, let c := loga b and define ga (x) as ga (x) := (1/c) · fa (x). We have ga (fa (x)) ≤

loga x fa (fa (x)) = = logb x. c c

Since fb (x) < fa (x), we have logb x = fb (fb (x)) < fb (fa (x)) and thus ga (x) = O(fb (x)). As the base of the logarithm does not affect the asymptotic behavior of fa (x), we will use f (x) instead of fa (x), wherever this is appropriate. While we cannot specify the asymptotic behavior of the half-logarithmic function f (x), we can sandwich f (x) between some easily representable functions. For any constant ϵ > 0, one can for example verify that 2 for h(x) = exp(lnϵ x), we have h(h(x)) = exp(lnϵ x) = ω(log x). Moreover, if we use the notation g (k) (x) to denote the k-fold application of a function g(x), we can define the following family of functions hk,ϵ for every integer k ≥ 1 and ϵ > 0: ϵ hk,ϵ (x) := exp(k) ln(k) x . (2)

For all fixed k and ϵ, one can verify that hk,ϵ (x) = ω(log n) and therefore hk,ϵ (x) = ω(f (x)) for the halflogarithm function f (x). Note that for every k ≥ 1, for every ϵ1 ∈ (0, 1) and every ϵ2 > 0, we have hk+1,ϵ1 (x) = o(hk,ϵ2 (x)) even if ϵ2 is much smaller than ϵ1 . For integers k ≥ 1 and constant c > 0, one can similarly build a family of functions ℓk,c as c ℓk,c (x) := exp(k) ln(k+1) x . (2)

Here, one can verify that for every k ≥ 1 and every c > 0, ℓk,c (x) = o(log x) and thus ℓk,c (x) = o(f (x)). In this case, as long as c > 1, for every k, we have ℓk+1,c (x) = ω(ℓk,c′ (x)) even if the constant c′ is chosen much larger than c.

LOCAL Without Extra Knowledge

To answer our question about how the LOCAL model is influenced by the initial knowledge provided to the nodes, we first investigate the most restrictive setting. In this section nodes are restricted to deterministic computation and are given unique IDs that are arbitrary natural numbers. Nodes are not provided with any other input, so they do not know anything about n and the IDs can be arbitrarily large. Note that without IDs we run into some trivial impossibilities and we do not want to restrict the model to the extent where problems become trivially unsolvable. Even though we kept our model strong enough to be able to still solve all considered problems, we will prove that this model is nevertheless too restrictive. We first prove that k-hierarchical 2 21 -coloring requires Ω(n) rounds. Note that in the LOCAL model O(n) rounds is a trivial upper bound for any solvable problem, since in O(n) rounds every node can learn the entire network with all inputs and brute force a solution through local computation. 17

We prove lower bounds for the two most extensively studied families of problems with polynomial complexities, namely k-hierarchical 2 21 -coloring and k-rake-and-compress. We start by defining a family of graphs, that we call k-hierarchical lower bound graphs. Definition 16 (k-hierarchical lower bound graph). Let ℓ1 , . . . , ℓk be positive integers. A k-hierarchical lower bound graph with parameters ℓ1 , . . . , ℓk is defined recursively as follows. Start from a path Pk of ℓk nodes. The path Pk is called path of level k, and its nodes are called nodes of level k. Let Tk = Pk . Then, recursively, for i = k − 1, . . . , 1 do the following. For each path Pi+1 of level i + 1, for each node v of Pi+1 : • if v has degree 2 in Ti+1 , create a path Pi of ℓi nodes, and connect one endpoint of Pi to v; • if v has degree 1 in Ti+1 , create two paths Pi , both of ℓi nodes, and for each Pi connect one endpoint of Pi to v. The paths Pi are paths of level i and their nodes are nodes of level i. Let Ti be the obtained graph. Q Observation 17. Let Li = 1≤j≤i ℓj . For some constants c1 ≥ 1 and c2 that depend solely on k, in a k-hierarchical lower bound graph with parameters ℓ1 , . . . , ℓk , each component of the subgraph induced by nodes of level at most i contains at least c1 · Li and at most c2 · Li nodes. Observation 18. Let G be a k-hierarchical lower bound graph. Then, any solution for k-hierarchical 2 21 coloring on G must satisfy that there exists an index i ∈ {1, . . . , k} and a path Pi of level i that is properly 2-colored. Proof. By induction on i, suppose that all nodes on all paths Pj for j < i are labeled D. By the definition of k-hierarchical 2 21 -coloring, either there exists a path Pi that is properly 2-colored, or all nodes on all paths Pi are also labeled D. Since the definition of k-hierarchical 2 12 -coloring does not allow nodes of Pk to be labeled D, we get that, if there is no path Pj for j < k that is properly 2-colored, then Pk is properly 2-colored. With this we can prove our first result. Theorem 1. For all integers k > 0, k-hierarchical 2 12 -coloring requires Ω(n) rounds, in the LOCAL model, where no bound on n, nor on the size of the ID space, is provided to the nodes. Proof. Let A be an algorithm that solves k-hierarchical 2 12 -coloring. Assume for a contradiction that for all ϵ > 0, for all integers n0 , there exists some n = f (ϵ, n0 ) > n0 , such that the algorithm A terminates in at most ϵn rounds on all n-node graphs. In Q the following, let c1 and c2 be the constants guaranteed to exist by Observation 17. Let L0 = 1 and Li = 1≤j≤i ℓj . Let Ni+1 = f ( 20c12 Li , 100c2 Li ) and ℓi+1 = ⌊Ni+1 /(c2 Li )⌋ for all i ∈ {0, . . . , k}. Observe that ℓi ≥ 100 for all i ∈ {1, . . . , k}. By assumption, in instances of size Ni the algorithm must terminate in at most Ni /(20c2 Li−1 ). Let G be the k-hierarchical lower bound graph with parameters ℓ1 , . . . , ℓk , labeled with an arbitrary ID assignment. Let Ti = ℓi /10. We prove by induction on i that, by running A on G, for each path Pi of level i it holds that there are two nodes u, v ∈ Pi satisfying the following properties: 1. both u and v are at distance at least Ti + 1 from the endpoints of Pi ; 2. u and v are at distance at least 2Ti + 1 from each other; 3. both u and v terminate in at most Ti rounds; 4. both u and v output D; The above properties, combined with the definition of k-hierarchical 2 12 -coloring, imply that the whole graph G is labeled D, which contradicts Observation 18 and hence proves the theorem. The base case i = 0 trivially holds (by the definition of the k-hierarchical lower bound graph, paths P0 do not exist). Let Pi be an arbitrary path of level i. Let u and v be the two nodes at distance exactly Ti + 1 from (at least) one of the endpoints of Pi . Nodes u and v clearly satisfy property 1. Since Pi has length ℓi , 18

since ℓi ≥ 100, and since u, v are at distance ℓi /10 + 1 from the endpoints, property 2 is also clearly satisfied. Assume for a contradiction that property 3 does not hold, and hence that u or v runs for strictly more than Ti rounds. W.l.o.g., let this node be v. We consider the graph G′ obtained by taking the connected component containing Pi in the subgraph of G induced by all nodes of level at most i. By Observation 17, G′ has at most c2 · Li nodes. Since ℓi ≤ Ni /(c2 Li−1 ), we get that G′ has at most Ni nodes. We modify G′ by taking an arbitrary path P1 at distance strictly larger than Ti from v and adding nodes in order to get a graph G′′ of exactly Ni nodes. By assumption, the algorithm A, when run on G′′ , must terminate in at most Ni /(20c2 Li−1 ) rounds. Since ℓi ≥ Ni /(c2 Li−1 ) − 1 ≥ Ni /(2c2 Li−1 ), we get that Ni ≤ 2c2 Li−1 ℓi . Hence, the algorithm must terminate in at most Ni /(20c2 Li−1 ) ≤ 2c2 Li−1 ℓi /(20c2 Li−1 ) = ℓi /10 = Ti rounds. Since within distance Ti the view of node v is the same on G and G′′ , and no additional input is provided to v, then the runtime of v must be at most Ti also on G, contradicting the assumption that on G node v runs for strictly more than Ti rounds, and hence proving property 3. We now prove that property 4 holds. Suppose for a contradiction that u or v output a label different from D. By the definition of the problem, since all nodes of lower layers are outputting D, it cannot be E, and hence it must be a color. By the constraints of the problem we get that Pi must be properly 2-colored. Let z be a node of Pi that is at distance strictly larger than Ti from both u and v and that lies on the path connecting u to v (which, by properties 1 and 2, must exist). Let z1 and z2 be the two neighbors of z in Pi . Consider the graph Ĝ obtained by removing from G the node z and all the nodes of lower layers reachable from it by not passing from z1 nor z2 , and then adding an edge connecting z1 and z2 . Observe that the view of u and v in Ĝ is the same as their view on G, and hence they run for the same time and they produce the same output. However, in Ĝ, the parity of the distance between u and v is different from the parity in G. Thus, the produced 2-coloring cannot be proper, reaching a contradiction and hence proving property 4. In the following, by rake node of level i (resp. compress node of level i) we denote a node with output label Ri (resp. Ci ). By type of a node we denote its output label. Before proving a result about k-rake-andcompress, we observe some useful properties about rake-and-compress decompositions. Lemma 19. Let v be a rake node of level i. Let t(u) be the type of node u in the k-rake-and-compress decomposition. Then, there must exist a path v1 , . . . , vl satisfying the following: • v1 is a node of degree ≤ 2; • vl = v; • t(vj ) ≤ t(vj+1 ) for all j, where the ordering is the one from Definition 15; • if vj is a rake node, it points to vj+1 . Proof. We prove that each node u of degree ≥ 3 must have at least one incoming edge. Since the graph is acyclic, and edges cannot be oriented from a layer to a strictly lower one, by recursively applying this idea starting from v, we obtain the lemma. If u is a rake node of degree ≥ 3, since all edges incident to u are oriented and at most one is outgoing, then the claim follows. If u is a compress node of degree ≥ 3, since at most 2 edges incident to u can be unoriented (because incident to other compress nodes), and all the other cannot be outgoing, then u has at least one incoming edge. By the fact that a rake node cannot have two outgoing edges, and the fact that an edge cannot be oriented from a larger level to a lower level, we observe the following. Observation 20. Let G be a graph. Any k-rake-and-compress decomposition of G must satisfy the following. Let P be a path that is a subgraph of G. Assume that all nodes of P are rake nodes (of possibly different levels). Then, there exists one node v in P such that all edges of P are oriented towards v. Moreover, for all nodes u ∈ P it must hold that t(u) ≤ t(v). This lets us prove our lower bound for computing a rake and compress decomposition. Theorem 2. For all integers k > 0, solving k-rake-and-compress requires Ω(n) rounds, in the LOCAL model, where no bound on n, nor on the size of the ID space, is provided to the nodes. 19

Proof. The proof of this theorem is similar to the proof of Theorem 1. Let A be an algorithm that solves k-rake-and-compress. Assume for a contradiction that for all ϵ > 0, for all integers n0 , there exists some n = f (ϵ, n0 ) > n0 , such that the algorithm A terminates in at most ϵn rounds on all n-node graphs. Let Li , ℓi , and Ti be defined as in the proof of Theorem 1. Let G be the k-hierarchical lower bound graph with parameters ℓ1 , . . . , ℓk , labeled with an arbitrary ID assignment. We prove by induction on i that, by running A on G, for each path Pi of level i the following holds. 1. There is at least one node with a compress label of level ≥ i. 2. If 1 ≤ i < k, let v be the endpoint of Pi that is connected to a node of Pi+1 . Then v is a rake node of level ≥ i + 1, or a compress node of level ≥ i. Observe that property 1 would imply that Pk contains at least one node labeled compress of level k, but by the definition of the problem, in a k-rake-and-compress decomposition, there are no compress nodes of level k, reaching a contradiction. The base case i = 0 of property 1 and 2 trivially holds (by the definition of the k-hierarchical lower bound graph, paths P0 do not exist). We start by proving that property 1 holds for i ≥ 1, assuming that property 2 holds for i − 1. Suppose for a contradiction, that there is no node labeled compress of level ≥ i. By property 2, all nodes connected to Pi from lower layers are rake nodes of layer ≥ i or compress nodes of layer ≥ i − 1. Since the only nodes of degree ≤ 2 are nodes of some P1 , we get that: • Nodes of Pi cannot be compress nodes of layer i − 1; • By Lemma 19, nodes of Pi are rake nodes of level ≥ i or compress nodes of level ≥ i. Note that the above statement is trivial for i = 1. By Observation 20, there must exist exactly one node v of Pi satisfying that all edges of Pi are oriented towards v. Similarly as in the proof of Theorem 1, we can modify G and create a different graph Ĝ such that we can pick some nodes in G that: they run in Ti rounds; they have the same view in G and in Ĝ and hence they produce the same output in G and in Ĝ; their output cannot be completed into a valid solution in Ĝ. This contradicts the correctness of A. We now prove that, assuming property 1 holds for i and property 2 holds for i − 1, property 2 holds also for i. Consider the subgraph G′ of G induced by all nodes belonging to paths of level strictly larger than i. By property 2, all nodes connected to Pi from lower layers are either rake nodes of layer ≥ i or compress nodes of layer ≥ i − 1. Since the only nodes of degree ≤ 2 are nodes of some P1 , we get that: • Nodes of Pi cannot be compress nodes of layer i − 1; • By Lemma 19, nodes of Pi are rake nodes of level ≥ i or compress nodes of level ≥ i. Note that the above statement is trivial for i = 1. Moreover, by the definition of k-hierarchical lower bound graph, all nodes of G′ are nodes of degree ≥ 3 in G. Let v be an arbitrary node in V (G) \ V (G′ ) that is connected to a node u ∈ V (G′ ). We prove that, either: • node v is a rake node of level ≥ i + 1 or a compress node of level ≥ i, or • node v is a rake node of level i and the edge {u, v} is oriented towards v. (We will later prove that this case cannot apply.) Suppose node v is not a rake node of level ≥ i + 1 nor a compress node of level ≥ i. This implies that v is a rake node of level exactly i. Let Pi be the path containing v, and let z be the compress node of layer i belonging to Pi that is the nearest to v, which, by property 1 must exist. Let w be the neighbor of z that is nearer to v. Let P be the subpath of Pi that starts at v and ends at w. If w is a rake node of level ≥ i + 1, by Observation 20 we get that the path P is not rooted at v. Since v cannot have two outgoing edges, we get that the edge {u, v} is oriented towards v. Otherwise, if w is a rake node of level exactly i, then the edge {w, z} is oriented towards z. By Observation 20, the path P is rooted on w. Again, since v cannot have two outgoing edges, we get that the edge {u, v} is oriented towards v. Let us summarize what we have observed so far. • Since all nodes in G′ have degree ≥ 3, there are no leaves in G′ . 20

• Let S be the set of nodes v ∈ V (G) \ V (G′ ) that have a neighbor u ∈ V (G′ ). Every v ∈ S is an endpoint of some Pi and is a rake node of level ≥ i or a compress node of level ≥ i. If v is a rake node of level exactly i, it must hold that the edge {u, v} is oriented towards v. We prove that each node v ∈ S is either a rake node of level ≥ i + 1 or a compress node of level ≥ i, establishing property 2. Suppose for a contradiction that there exists a node v ∈ S that is a rake node of level exactly i. By Lemma 19, and the fact that v cannot have two outgoing edges, there must exist a path v1 , . . . , vl that starts from a node of degree ≤ 2, contains at least one node of G′ , and ends at v, such that t(vj ) ≤ t(vj+1 ) for all j and such that if vj is a rake node, then it points to vj+1 . However, by the above observations, in order for such a path to start from a node of degree ≤ 2 (and hence a node of some P1 ) and reach a node of G′ , it must contain some rake node of level ≥ i + 1 or some compress node of level ≥ i. Since v is a rake node of level i, this contradicts the ordering on the path.

Polynomial Upper Bound N Given

In this section, we consider the model in which nodes are provided with some integer N and the promise that n ≤ N ≤ nc for some positive integer c. Nodes do not know the value of n, but they know c. For some value of γ to be specified later, we provide an upper bound of O(γ) for computing a (γ, ℓ, k)1 decomposition. By Lemma 12, such an upper bound applies also to all problems that have complexity o(n k−1 ) in the standard LOCAL model. The value of γ will depend on the result of a nontrivial optimization problem. Hence, we now provide an informal statement, and we will provide the precise statement in Corollary 29. Lemma 21. For any positive integer k, there exists some constant α < 1c , such that a (O(ncα ), ℓ, k)decomposition can be computed in O(ncα ) rounds. Our algorithm starts by doing N α rakes and then a compress. The main idea is that we may do a lot of work upfront if our bound N is bad. That is if N is close to nc , we might already spend a lot of time doing this first set of rakes. However, this also means that we make a lot of progress and so we might be able to be more aggressive afterwards. We push this idea to the limit, by starting with a fully parameterized algorithm and choosing the parameters based on an optimization problem.

4.1

The Decomposition Algorithm

Fix positive integers k and c. The algorithm is parameterized by some parameters α1 , . . . , αk−1 that can be computed solely as a function of k and c, and computes a (γ, ℓ, k)-decomposition for γ ∈ O(ncα1 ). Recall that an integer N satisfying n ≤ N ≤ nc is provided to the nodes. Recall that a rake operation is the removal of all nodes of degree 0 or 1, and that a compress operation consists of the removal of all connected components containing at least ℓ nodes and consisting of nodes of degree exactly 2. The algorithm consists of the following k phases. • Phase 1 ≤ i < k: Perform N αi rakes and then a single compress. • Phase k: Perform rakes until the graph becomes empty. In order to analyze this algorithm, we use the following lemma, which has been proven in [23]. This lemma upper bounds the number of nodes that remain after performing some number of rake operations followed by a single compress operation. Lemma 22 ([23]). Given a forest with n nodes, by performing x rakes and 1 compress with minimum path ℓ length ℓ, the number of remaining nodes is at most 2x n. As a simple corollary of Lemma 22, we get bounds on the number of nodes that are still present after phase i. Pi Corollary 23. For any 1 ≤ i < k, let Ai := j=1 αj . Then, after phase i of the execution of the algorithm, at most O NnAi nodes remain.

By using Corollary 23, we can derive an upper bound on the runtime of a given phase. o n rounds. Lemma 24. For any 1 ≤ i < k, phase i of the algorithm takes at most O min N Ani−1 , N αi n Furthermore, phase k takes at most O N Ak−1 rounds. Proof. By Corollary 23, at the beginning of phase 2 ≤ i ≤ k, only O

N Ai−1

nodes remain. Also, every

αi

phase, except phase k, can run for at most O(N ) rounds, because each rake operation, and the compress operation, can be performed in a constant number of rounds. The runtime of our algorithm depends on the parameters α1 , . . . , αk−1 . In order to determine the correct choice for these parameters, we introduce and analyze an optimization problem in the next section.

4.2

The Optimization Problem

Lemma 24 gives rise to the following optimization problem, where we want to optimize the parameters α1 , . . . , αk−1 to make the overall runtime as small as possible. Parameters.

The following parameters are constants of the problem instance:

• The number of nodes n. This parameter is not known by the nodes, and hence the values of αi cannot be computed as a function of it. • The integer k. This parameter depends on the problem that the nodes need to solve, and hence it is known by the nodes. The following parameters are given adversarially: • The exponent c and the integer N . These parameters are known by the nodes, and it is guaranteed that n ≤ N ≤ nc . We need to determine the values of the following parameters: • The integers α1 , . . . , αk−1 . Recall that these parameters govern the number of rakes performed during each phase. That is, at phase i, nodes perform N αi rakes. Pi In the following, recall that Ai is defined as Ai := j=1 αj . Moreover, by ᾱ we denote the vector [α1 , . . . , αk−1 ]. Optimization Problem. Since the number of phases of our algorithm is k, and since k is constant, the runtime of our algorithm is given by the runtime of its slowest phase. Hence, for 1 ≤ i ≤ k, let Ti be the runtime of the ith phase, as a function of all the other parameters. The goal is to minimize the largest Ti , for the worst-case choice of n and N . Hence, we get that the overall runtime of the algorithm is bounded by the optimal solution to the following optimization problem.   T1 := N α1       n α2   , N T := min   α1 2 N       ... n o min max c n αi ᾱ N ∈[n,n ]  Ti := min ,N    N Ai−1       . . .       1−Ak−1 Tk := n Just from the statement alone we can immediately see that we get an algorithm with complexity at least polynomially faster than O(n). Corollary 25. Let ᾱ be an optimal solution to the optimization problem then for 1 ≤ i ≤ k − 1 it holds that c αi < 1c and also all Ti ∈ O(nε ) for some ε ≤ c+1 . 22

Proof. We simply give a valid assignment to ᾱ, that is not optimal but still gives us a (rough) upperbound on the optimal solution. 1 = α1 = α2 = . . . = αk−1 . Then all of the Ti , except Tk are bounded by Let c+1 1

N αi ≤ nc· c+1 = n c+1 For Tk we have

Tk = n1−Ak−1 = n1−(k−1) c+1 < n1− c+1 = n c+1

Since any optimal solution must be at least as good as this one, the statement follows. The rest of this section is devoted to finding a precise solution to the optimization problem. We try to reduce the complexity of the problem one step at a time, by first eliminating the minimization terms inside of the Ti terms. k j Lemma 26. Let i0 := cα1 1 . Then, the optimal values of αi satisfy α1 = . . . = αi0 . Moreover, as a result, it holds that Ai = i · α1 for all 1 ≤ i ≤ i0 . Proof. If we fix ᾱ, then the runtime Ti of phase i is maximized if N = nbi for some worst case 1 ≤ bi ≤ c. We solve for bi , by setting the terms in the minimization equal to each other. n n o n n o αi bi ·αi Ti := max c min , N = max min , n n≤N ≤n 1≤bi ≤c N Ai−1 nbi ·Ai−1 n ⇐⇒ bi ·Ai−1 = nbi ·αi n ⇐⇒ 1 − bi · Ai−1 = bi · αi 1 1 ⇐⇒ bi = = Ai−1 + αi Ai However, bi cannot be larger than c and since all αi are strictly positive, the Ai terms are strictly increasing. As a result we might have to set bi = c < 1/Ai which leads to nbi Ani−1 > nbi αi . So because Ti is the minimum of these two terms we obtain the following: 1 bi = min c, Ai ( bi αi n if bi = c Ti = n bi αi =n , if bi = A1i nbi Ai−1 In the former case, i.e., when bi = c, the runtime Ti becomes ncαi . Hence, we get that for all i such that bi = c, the runtime Ti is ncαi and hence, for all such i, the values of αi are all the same. Now we only need to show that the αi for which bi = c are exactly α1 = α2 = . . . = αi0 . Because the Ai are strictly increasing by increasing i, there is some cutoff point at which A1i becomes less than c. Let i0 be that index, and more specifically, let i0 be the index satisfying that bi0 = c and bi0 +1 = Ai1+1 . We get that α1 = α2 = . . . = αi0 , and hence for all i ≤ i0 we get that Ai = i · α1 . 0 o n Moreover, since bi = min c, A1i , we get that bi = c ⇐⇒ c ≤ A1i = Ai−11+αi . We thus get that bi = c ⇐⇒ cα1 ≤ 1 − c(i − 1)α1 (the exponents in the definition of Ti ). By solving for i, we obtain the following: cα1 ≤ 1 − c(i − 1)α1 1 ⇐⇒ i ≤ cα1 This implies that

1 i0 = , cα1 since i0 must be an integer. 23

Lemma 27. Let i0 :=

1 cα1

k cα1 . Then, for each i0 < i ≤ k−1, the optimal value of αi satisfies αi = 1−cα Ai−1 . 1

1 Ai−1 . Moreover, for i0 < i ≤ k − 1, it holds that Ai = 1−cα 1

Proof. By Lemma 26 and the arguments used in its proof, we know that, for all 1 ≤ i ≤ i0 , the worst-case value of Ti is obtained by using bi = c, and by using such a value we obtain that all Ti , for 1 ≤ i ≤ i0 , are equal to T1 = ncα1 . Hence, in order to optimize the values of Ti for i0 < i < k, we set Ti equal to T1 and derive αi . Recall that, for all i0 < i < k, we proved that Ti = nαi /Ai . By setting T1 equal to Ti for each i0 < i < k, we thus get the following. ncα1 = nαi /Ai αi ⇐⇒ cα1 = Ai ⇐⇒ αi = cα1 (αi + Ai−1 ) cα1 ⇐⇒ αi = Ai−1 1 − cα1 From this it follows that, for all i0 < i ≤ k − 1, cα1 Ai−1 1 − cα1 1 ⇐⇒ Ai = Ai−1 1 − cα1

Ai − Ai−1 = αi =

Lemma 28. The optimal value of α1 satisfies 1 =

1 1−cα1

k−i0

i0 α1 .

Proof. We use Lemmas 26 and 27 to express Ak−1 in terms of i0 and α1 . k−1−i0 1 Ak−1 = Ai 0 1 − cα1 k−1−i0 1 = i0 α1 1 − cα1 By setting T1 = Tk , we get that ncα1 = n1−Ak−1 . Hence, we obtain the following. ncα1 = n1−Ak−1 ⇐⇒

cα1 = 1 − Ak−1 ⇐⇒ 1 − cα1 = Ak−1 = ⇐⇒

1 1 − cα1

k−1−i0 1 i0 α1 1 − cα1 k−i0 i0 α1

By combining Lemmas 26 to 28, and by observing that in each phase the algorithm performs at most O(ncα1 ) rakes, we obtain the following. Corollary 29. The algorithm described in Section 4.1 computes a (γ, ℓ, k)-decomposition, for some γ ∈ k−i0 j k 1 1 O(ncα1 ), in O(ncα1 ) rounds, where α1 is the unique value satisfying 1 = 1−cα i α , and i := . 0 1 0 cα 1 1 Proof. The algorithm described in Section 4.1 satisfies the desired runtime when using the parameters provided by the optimization problem. What is left to show is that there exists a unique real solution. For this we will first prove, that the function k−i0 1 i0 α1 − 1 f (α1 ) = 1 − cα1 24

is continuous on the interval (0, 1c ) and then that it is monotonically increasing. The only part of f k j argue, 1 cα1

that is not continuous, is i0 . Since i0 :=

1 , i0 makes jumps at α1 = tc =: βt , for all t ∈ N>1 . Hence,

if we prove f is continuous in these points, then f is continuous on all of (0, 1c ). Let us compute the left 1 1 t and right limits of f at βt . First, notice that the limit of 1−cα exists at βt and is equal to 1−c/(tc) = t−1 . 1 Therefore we have the following: k−(t−1) k−(t−1) k−t 1 t t t−1 1 t (t − 1)βt − 1 = −1 lim f (α1 ) = −1= t−1 c t−1 t c t−1 α1 →βt+ and lim f (α1 ) =

α1 →βt−

t t−1

k−t

1 tβt − 1 = c

t t−1

k−t − 1.

The two limits are equal, therefore f is continuous at βt for every t, and hence f is continuous on (0, 1c ). Now, let us prove that f is monotonically increasing. Since f is continuous and differentiable on the intervals (βt+1 , βt ), we will just differentiate f on these intervals and show that the derivative is nonnegative. k−t 1 Moreover, notice that on the interval (βt+1 , βt ), i0 = t. Let gt (x) = 1−cx tx − 1. Then its derivative g ′ is, by the standard rules of differentiation: gt′ (x) = t(1 − cx)t−k + tx(t − k)(−c)(1 − cx)t−k−1 = t(1 − cx)t−k−1 (1 − cx + cx(k − t)). Let us show that gt′ (x) > 0 for x ∈ (βt+1 , βt ) ∩ (0, 1/c) (remember that we require α1 < 1/c). As x < 1/c, we have that t(1 − cx)t−k−1 > 0. Moreover, 1 − cx + cx(k − t) > 0 ⇔ 1 > cx(1 − k + t). We know that cx < c/c = 1 and t ≤ k, i.e. 1 − k + t ≤ 1. Therefore, g ′ is nonnegative on (βt+1 , βt ) ∩ (0, 1/c) and only one solution to f (α1 ) = 0 can exist. Therefore, α1 is unique. Is it know left to show that α1 exists. For this, we use the Intermediate Value Theorem. lLet mus compute the limits of f (α1 ) towards 0 and 1/c. Let us first compute limα1 →0+ f (α1 ). Let i0 (α1 ) =

1 cα1

. There is some function δ(α1 ) such that for all α1 ,

δ(α1 ) ∈ [0, 1) and such that i0 (α1 ) = cα1 1 − δ(α1 ). First, lim + i0 (α1 )α1 = lim +

α1 →0

1 1 1 − δ(α1 ) α1 = lim + − δ(α1 )α1 = . cα1 c α1 →0 c

Now, we focus on computing limα1 →0+ (1 − cα1 )i0 (α1 )−k . Rewrite (1 − cα1 )i0 (α1 )−k = exp ((i0 (α1 ) − k) ln(1 − cα1 )) . We have that (i0 (α1 ) − k) ln(1 − cα1 ) ∼α1 →0+

1 − δ(α1 ) − k (−cα1 ) −→α1 →0+ −1 + lim + (δ(α1 ) + k)α1 = −1 cα1 α1 →0

as k and δ(α1 ) are bounded. Finally, we get that limα1 →0+ (1 − cα1 )i0 (α1 )−k = 1e and that lim f (α1 ) =

α1 →0+

1 − 1 < 0. ce

Now, let us compute limα1 →1/c− f (α1 ). First, notice that limα1 →1/c− i0 (α1 ) = 1. Therefore, if it exists, lim − f (α1 ) = −1 +

α1 →1/c

1 lim (1 − cα1 )1−k . c α1 →1/c−

As k > 1 and (1 − cα1 ) −→α1 →1/c− 0+ , we get limα1 →1/c− (1 − cα1 )1−k = +∞, and lim

α1 →1/c−

f (α1 ) = +∞.

1 Intermediate Value Theorem, as 0 ∈ ce − 1, +∞ , and as f is continuous, α1 , which is the solution to f (α1 ) = 0, exists. This finishes the proof. 25

By invoking Lemma 12 we get that all LCLs can be solved in that round complexity, note that the O(log∗ I) term comes from the compress precomputation (see Section 2.4). 1

(1) (2) (3) (4)

Proof. Fact (1) follows from the prove of Lemma 27, where we set ncα1 = nαi /Ai For Fact (2): αi =

cα1 1 αi−1 1 Ai−1 = · · Ai−1 = αi−1 1 − cα1 1 − cα1 Ai−1 1 − cα1

Then Fact (3) follows directly from Fact (2), by observing that cα1 < 1 For Fact (4) we start with (1) and get αi = α1 c Ai 1 αi ⇐⇒ Ai = c α1 By Lemma 26 and Fact (3) it follows that αi > α1 and so (4) follows.

Lower Bound for the Case in Which a Polynomial Upper Bound on n is Given

Next we show that our algorithm from Section 4.1 is actually optimal. This is interesting as it essentially implies that our algorithm exploits the given information as much as possible. So the tradeoff between upfront work and exploiting the knowledge obtained during earlier rounds is optimal. Note that we have essentially captured the inner workings of this tradeoff in the optimization problem. As such, we will also refer to it often when proving our lower bounds. In this section, we prove lower bounds for the setting in which nodes are provided with some integer N and the promise that: • n ≤ N ≤ nc for some positive integer c, and nodes do not know n but they know c.

• IDs are from {1, . . . , N }. While the lower bounds of Section 3 hold using Knuth’s definition of Ω, in this section we prove lower bounds using Hardy-Littlewood’s definition of Ω. For more information on those definitions, refer to Section 2.5.1. We start by proving that such weaker statements are necessary, since no improved lower bounds can be obtained for Knuth’s definition of Ω.

5.1

An Algorithm That Requires O(n1/k ) Rounds for Infinitely Many Values of n

We prove that, for the setting considered in this section, for infinitely many values of n, it is possible to compute a (γ, ℓ, k)-decomposition in O(γ) rounds for γ ∈ O(n1/k ). This implies that, for Knuth’s definition of Ω, the (γ, ℓ, k)-decomposition problem is not in Ω(T ), for any T that is asymptotically strictly larger than n1/k . By Lemma 12, the same statement will then hold for all LCLs that in the standard LOCAL model have complexity O(n1/k ), and in particular for k-hierarchical 2 21 -coloring. Lemma 31. Let Π be the problem of computing a (γ(n), ℓ, k)-decomposition satisfying that for all n, γ(n) = O(n), but for infinitely many values of n, γ(n) = O(n1/k ). For Knuth’s definition of Ω, the problem Π is not in Ω(T ), for any T that is asymptotically strictly larger than n1/k . Proof. We prove that for infinitely many values of n, it is possible to compute a (γ(n), ℓ, k)-decomposition in O(γ(n)) rounds, for γ(n) ∈ O(n1/k ). For all the other values of n, γ(n) will be in O(n). Let S = s1 , s2 , . . . be the sequence defined as follows. si = 2 if i = 1 si = s2c i−1 otherwise The algorithm receives as input N , which is guaranteed to satisfy n ≤ N ≤ nc . Recall that c is known by the algorithm, and that all nodes receive the same value of N . The nodes compute S ∗ = S ∩{⌊N 1/c ⌋, . . . , N }. Observe that, by the definition of S, it either holds that S ∗ is empty or that it contains a single element s. Let X = N if S ∗ is empty, and let X = s otherwise. The algorithm, for k − 1 times, performs X 1/k rakes and a single compress. Then, it performs rakes until the graph becomes empty. Each of the k − 1 phases n ). costs O(X 1/k ) rounds. After the k − 1 phases, by Lemma 22, the number of remaining nodes is O( X (k−1)/k n 1/k Hence, the runtime of the algorithm is O max X (k−1)/k , X . While the runtime of the algorithm is clearly O(n) and the algorithm clearly computes a (O(n), ℓ, k)-decomposition, observe that, if n = si for some i, then X = n, and hence for infinitely many values of n it holds that X = n, the runtime is O(n1/k ), and the result is a (O(n1/k ), ℓ, k)-decomposition. By combining Lemma 31 with Lemma 12, we obtain our theorem. 1

Theorem 6. Let Π be an LCL problem that, on trees, has complexity Θ(n k ) in the LOCAL model, when nodes are provided with a linear upper bound on n and IDs are from some polynomial range. Consider the LOCAL model where nodes are provided N and c, such that N is guaranteed to satisfy n ≤ N ≤ nc . Then, for Knuth’s definition of Ω, the problem Π is not solvable in Ω(T + log∗ I) rounds, for any T that is asymptotically strictly larger than n1/k , where I is the largest ID assigned to any node. Observe that Theorem 6 applies to k-hierarchical 2 12 -coloring as well.

5.2

Lower Bound for k-Hierarchical 2 21 -coloring

We now prove that, according to the Hardy-Littlewood’s definition of Ω, the algorithm for k-hierarchical 2 12 -coloring guaranteed to exist by Corollary 29 and Lemma 12 is tight. More specifically, we devote the rest of the section in proving the following theorem.

Theorem 4. Consider the LOCAL model where nodes are provided N and c, such that N is guaranteed to satisfy n ≤ N ≤ nc , and nodes are assigned unique IDs in {1, . . . , nc }. Let α1 < 1c be the unique value k−i0 k j 1 1 . i α , where i := satisfying 1 = 1−cα 0 1 0 cα 1 1 Then, for the Hardy-Littlewood definition of Ω, the k-hierarchical 2 12 -coloring problem requires Ω(ncα1 ) deterministic rounds. We start by proving that, similarly as in the proof of Theorem 1, if all nodes below some layer i output D, then also nodes at layer i output D, unless they spend some large runtime. Lemma 32. Let A be an algorithm for k-hierarchical 2 12 -coloring, let G be a k-hierarchical lower bound graph with parameters ℓ1 , . . . , ℓk and an arbitrary ID assignment, and let 1 ≤ i ≤ k be an integer parameter. Suppose A, on G, outputs D on all nodes of level < i. Then, either: • A outputs D on all nodes of level i, or • at least one node z of level i outputs B or W , runs for strictly more than ⌈ℓi /8⌉ rounds, and is at distance strictly larger than ⌈ℓi /8⌉ from the endpoints of the path containing z. Proof. Suppose that at least one node of level i does not output D. Then, there must exist a path P of level i containing a node w that does not output D. Since all nodes of levels < i output D, the output of w cannot be E, and hence it must be B or W . By the constraints of the problem we get that P must be properly 2-colored. Suppose for a contradiction that all nodes of P run for at most T = ⌈ℓi /8⌉ rounds. We modify G to create a new instance G′ as follows. Let u and v be two nodes of P satisfying the following: • both u and v are at distance at least T + 1 from the endpoints of P ; • u and v are at distance at least 2T + 1 from each other. Let z be an arbitrary node that lies between u and v in P , and such that it is at distance at least T + 1 from both u and v. Let z1 and z2 be the two neighbors of z in P . We create G′ as follows: • remove the edges {z, z1 } and {z, z2 }; • add the edge {z1 , z2 }; • add an edge {x, z} for an arbitrary node x that is at distance at least T + 1 from both u and v. We obtain that the parity of the distances between u and v is different in G and in G′ , but their view in T rounds is the same. Hence, A must fail either in G or in G′ in producing a 2-coloring of the path containing them, reaching a contradiction. We now prove Theorem 4. For a contradiction, assume that there exists a deterministic algorithm A with runtime T (n) ∈ o(ncα1 ). As a result, for any ε > 0, there must exist an integer n0 = f (ε) such that, for all n ≥ n0 , it holds that T (n) ≤ εncα1 . 1 Let β be the constant c2 guaranteed to exist by Observation 17. Let ε = 100βσ for some constant σ ≥ 1 to be fixed later, and let n0 = f (ε). We first create an instance G of the k-hierarchical lower bound graph αk−1 1−A α2 1 with parameters ℓ1 = ⌈nα ⌉, ℓk = ⌈n1 k−1 ⌉, where n1 = nc0 and the values 1 ⌉, ℓ2 = ⌈n1 ⌉, . . . , ℓk−1 = ⌈n1 of αi are given by Lemmas 26 and 27. Let n be the number of nodes of G. By Observation 17, n1 ≤ n ≤ βn1 . We set N = n and assign IDs 1, . . . , n to the nodes of G arbitrarily. We prove by induction on i that, on G, for all levels 1 ≤ i ≤ k − 1, all nodes of layer ≤ i output D. We will later prove that this implies a contradiction for the nodes at level k. We start by considering the base case i = 1. Claim 33. All level 1 nodes of G output D. Proof. Assume for a contradiction that at least one node v of level 1 does not output D. Let P be the path containing v, and let T = ⌈ℓ1 /8⌉ + 1. By Lemma 32, this implies that there is at least one node v satisfying the following: 28

• Node v is at distance at least T from the endpoints of P ; • Node v runs for at least T rounds. We construct a new instance G′ of n̄ = ⌈n1/c ⌉ nodes as follows: • Start from the radius-T neighborhood of v, which is a path P ′ of 2T + 1 < 21 nα1 ≤ 12 n̂ nodes; (α1 < 1c by Corollary 25) • Connect a path P ′′ of n̄ − (2T + 1) nodes to an arbitrary endpoint of P ′ ; • Assign to the nodes of P ′′ arbitrary IDs from {1, . . . , n} that are not used in P ′ . We now run A on G′ by giving N = n to the nodes. Observe that this is an allowed input, since: • The instance G′ has n̄ nodes, and it holds that n̄ ≤ N = n ≤ ⌈n1/c ⌉c = n̄c . • IDs are in {1, . . . , N }. Moreover, observe that the radius-T neighborhood of v is the same in both G and G′ , and the given N is the same in both instances. Hence, node v runs for at least T rounds also on G′ . 1/c Observe that n̄ = ⌈n1/c ⌉ ≥ ⌈n1 ⌉ = ⌈(nc0 )1/c ⌉ = n0 . Hence, by assumption, node v must terminate in at 1 cα1 most T ≤ 100βσ n̄ rounds, for σ ≥ 1. We thus get that the runtime T of v satisfies: 1 α1 1 1 α1 1 • T ≥ ⌈ℓ1 /8⌉ + 1 ≥ ⌈nα + 1 ≥ 50β nα1 + 1; 1 /8⌉ + 1 ≥ ⌈ 8β n ⌉ + 1 ≥ 8β n 1 1 1 1 • T ≤ 100β n̄cα1 = 100β ⌈n1/c ⌉cα1 ≤ 50β (n1/c )cα1 = 50β nα1 .

Hence, we reach a contradiction. We now consider the inductive step. That is, assuming that all nodes of levels < i output D, we prove that all nodes of level i output D as well. Claim 34. Let i be an integer satisfying 2 ≤ i ≤ k − 1. Assume that, on G, all nodes of level < i output D. Then, all nodes of level i output D. Proof. By assumption, all nodes of level < i output D. Assume for a contradiction that at least one node v of level i does not output D. Let P be the path containing v, and let T = ⌈ℓi /8⌉ + 1. By Lemma 32, this implies that there is at least one node v of level i satisfying the following: • Node v is at distance at least T from the endpoints of P ; • Node v runs for at least T rounds. Similarly as in the proof of Claim 33, we will construct a new instance G′ . However, this time, the value of n̄ will depend on i. We start by proving an upper bound of n∗ = min{n, σ⌈nAi ⌉} on the number of nodes in the radius-T neighborhood of v, where σ ≥ 1 is a large enough constant (which depends on k) to be fixed later. By Observation 17, and the fact that v is at distance at least T from the endpoints of P , the nodes in the radius-T neighborhood of v are at most: Y A (2T + 1) ℓj ≤ (2T + 1)2k−1 n1 i−1 ≤ (2T + 1)2k−1 nAi−1 ≤ σnAi , for large enough σ. 1≤j≤i−1

In order to construct G′ , we consider two separate cases, namely the case in which i ≤ i0 and the case in which i > i0 .

• Case i ≤ i0 . By Lemma 26, it holds that Ai = i · α1 and αi = α1 . We thus obtain the following. j k 1 ·α n∗ ≤ σ⌈ni·α1 ⌉ ≤ σ⌈ni0 ·αi ⌉ < σ n cα1 i 1

< σ⌈n cα1 ·αi ⌉ = σ⌈n c ⌉ We choose n̄ = min{n, σ⌈n1/c ⌉}, and we obtain G′ by taking the radius-T neighborhood of v and adding nodes in order to get exactly n̄ nodes, in such a way that the radius-T neighborhood of v does not change (i.e., we connect a path to an arbitrary node at distance exactly T from v, which exists in P ). To the added nodes we assign unused IDs from {1, . . . , n}. We now run A on G′ by giving N = n to the nodes. Observe that this is an allowed input, since: – The instance G′ has n̄ nodes, and it holds that n̄ ≤ N = n ≤ min{n, (σ⌈n1/c ⌉)c } ≤ n̄c . – IDs are in {1, . . . , N }. Moreover, observe that the radius-T neighborhood of v is the same in both G and G′ , and the given N is the same in both instances. Hence, node v runs for at least T rounds also on G′ . 1 Observe that n̄ ≥ n0 . Hence, by assumption, node v must terminate in at most T ≤ 100βσ n̄cα1 rounds. We thus get that the runtime T of v satisfies: 1 αi 1 1 αi i + 1 ≥ 50β nα1 + 1; – T ≥ ⌈ℓi /8⌉ + 1 ≥ ⌈nα 1 /8⌉ + 1 ≥ ⌈ 8β n ⌉ + 1 ≥ 8β n 1 1 1 1 – T ≤ 100βσ n̄cα1 ≤ 100βσ (σ⌈n1/c ⌉)cα1 ≤ 50β (n1/c )cα1 = 50β nα1 .

Hence, we reach a contradiction. αi • Case i > i0 . By Lemma 30, we know that Ai ≥ 1/c and that A = α1 · c. We choose n̄ = n∗ , and i ′ similarly as before we obtain G by taking the radius-T neighborhood of v and adding nodes in order to get exactly n̄ nodes, using IDs from {1, . . . , n}, in a way that satisfies that the radius-T neighborhood of v does not change. Again, we run A on G′ by giving N = n to the nodes. Observe that this is an allowed input, since:

– The instance G′ has n̄ nodes, and it holds that n̄ ≤ N = n ≤ min{n, (σ⌈nAi ⌉)c } ≤ n̄c , where the second inequality holds because Ai ≥ 1/c. – IDs are in {1, . . . , N }. Moreover, observe that the radius-T neighborhood of v is the same in both G and G′ , and the given N is the same in both instances. Hence, node v runs for at least T rounds also on G′ . Observe that n̄ = min{n, σ⌈nAi ⌉} ≥ min{n, ⌈n1/c ⌉} ≥ min{n, ⌈(nc0 )1/c ⌉} ≥ n0 . Hence, by assumption, 1 node v must terminate in at most T ≤ 100βσ n̄cα1 rounds. We thus get that the runtime T of v satisfies: 1 αi 1 αi 1 i nαi + 1; – T ≥ ⌈ℓi /8⌉ + 1 ≥ ⌈nα + 1 ≥ 50β 1 /8⌉ + 1 ≥ ⌈ 8β n ⌉ + 1 ≥ 8β n αi

αi

1 1 1 1 – T ≤ 100βσ n̄cα1 = 100βσ n̄ Ai ≤ 100βσ (σ⌈nAi ⌉) Ai ≤ 50β nαi .

Hence, we reach a contradiction.

By combining Claim 33 with Claim 34 we obtain that, on G, all nodes in levels 1, . . . , k − 1 output D. Consider the nodes of G at level k. They form a path P of length ℓk . Since D is not allowed on nodes of level k, by Lemma 32 we obtain that at least one node v in P must spend at least ⌈ℓk /8⌉ rounds. We thus get that the runtime T of v satisfies: 1−A

1 cα1 1 cα1 1 1 • T ≥ ⌈ℓ1 /8⌉ + 1 ≥ ⌈n1 k−1 /8⌉ + 1 = ⌈ncα ⌉ + 1 ≥ 8β n + 1 ≥ 100β ncα1 + 1, where 1 /8⌉ + 1 ≥ ⌈ 8β n 1 − Ak−1 = α1 c is given by the optimization problem (Lemma 28); 1 1 • T ≤ 100βσ ncα1 ≤ 100β ncα1 .

Hence, we reach a contradiction. So the Theorem is proven. 30

5.3

Lower Bound for k-Rake-and-Compress Decomposition

We now prove that the lower bound of Theorem 4 holds for k-rake-and-compress decomposition as well. Theorem 5. Consider the LOCAL model where nodes are provided N and c, such that N is guaranteed to satisfy n ≤ N ≤ nc , and nodes are assigned unique IDs in {1, . . . , nc }. Let α1 < 1c be the unique value k−i0 j k 1 1 i α , where i := satisfying 1 = 1−cα 0 1 0 cα1 . 1 Then, for the Hardy-Littlewood’s definition of Ω, the k-rake-and-compress decomposition problem requires Ω(ncα1 ) deterministic rounds. We devote the rest of the section to proving Theorem 5. The proof of such theorem will borrow ideas from the proofs of Theorems 2 and 4. We start by proving a lemma similar to Lemma 32. Lemma 35. Let i ≥ 1, and let Pi be a path of level i in a k-hierarchical lower bound graph. Assume that all nodes of lower layers connected to nodes of Pi are rake nodes of level ≥ i or compress nodes of level ≥ i − 1. Then, either: • there is at least one node of Pi labeled compress node of level ≥ i, or • at least one node z of Pi runs for strictly more than ⌈ℓi /8⌉ rounds, and is at distance strictly larger than ⌈ℓi /8⌉ from the endpoints of Pi . Proof. The proof follows by applying the same ideas used in the proof of Theorem 2. Suppose for a contradiction that there is no node labeled compress of level ≥ i and that all nodes of Pi (and far enough from the endpoints) run for at most ⌈ℓi /8⌉ rounds. By assumption, all nodes connected to Pi from lower layers are rake nodes of layer ≥ i or compress nodes of layer ≥ i − 1. Observe that no node of Pi can be a compress node of layer i − 1, since, in the subgraph induced by Pi and all nodes connected to at least one node of Pi , nodes of Pi have degree ≥ 3. Hence, by Lemma 19, all nodes of Pi must be rake nodes of layer ≥ i. By Observation 20, there must exist exactly one node v of Pi satisfying that all edges of Pi are oriented towards v. As argued in Theorem 2 and in Theorem 2, if all nodes of Pi (far enough from the endpoints) have a runtime that is sufficiently smaller compared with the length of Pi , then we can create a new instance that gives a contradiction with the correctness of the algorithm. We now prove Theorem 5. For a contradiction, assume that there exists a deterministic algorithm A with runtime T (n) ∈ o(ncα1 ). As a result, for any ε > 0, there must exist an integer n0 = f (ε) such that, for all n ≥ n0 , it holds that T (n) ≤ εncα1 . 1 Let β be the constant c2 guaranteed to exist by Observation 17. Let ε = 100βσ for some constant σ ≥ 1 to be fixed later, and let n0 = f (ε). We first create an instance G of the k-hierarchical lower bound graph αk−1 1−A α2 1 with parameters ℓ1 = ⌈nα ⌉, ℓk = ⌈n1 k−1 ⌉, where n1 = nc0 and the values 1 ⌉, ℓ2 = ⌈n1 ⌉, . . . , ℓk−1 = ⌈n1 of αi are given by Lemmas 26 and 27. Let n be the number of nodes of G. By Observation 17, n1 ≤ n ≤ βn1 . We set N = n and assign IDs 1, . . . , n to the nodes of G arbitrarily. We prove by induction on i that, on G, for all levels 1 ≤ i ≤ k − 1, for all Pi , if v is the endpoint of Pi that is connected to a node of Pi+1 , then v is a rake node of level ≥ i + 1 or a compress node of level ≥ i. We will later show that this gives a contradiction on Pk . We start by considering the base case i = 1. Claim 36. For all P1 , if v is the endpoint of P1 that is connected to a node of P2 , then v is a rake node of level ≥ 2 or a compress node of level ≥ 1. Proof. We start by proving that P1 contains at least one node labeled compress node of level ≥ 1. Assume for a contradiction that P1 contains only rake nodes. By Lemma 35, this implies that there is at least one node z of P1 satisfying the following: • Node z is at distance at least T from the endpoints of P1 ; • Node z runs for at least T rounds. From these assumptions, we can reach a contradiction in the exact same way as in the proof of Claim 33. Hence, P1 contains at least one node labeled compress node of level ≥ 1. As shown in the proof of Theorem 2, this implies that v is a rake node of level ≥ 2 or a compress node of level ≥ 1. 31

We now consider the inductive step. Claim 37. Let 1 ≤ i ≤ k − 1. Assume that, for all j < i, it holds that, for all Pj , if v is the endpoint of Pj that is connected to a node of Pj+1 , then v is a rake node of level ≥ j + 1 or a compress node of level ≥ j. Then, for all Pi , if v is the endpoint of Pi that is connected to a node of Pi+1 , then v is a rake node of level ≥ i + 1 or a compress node of level ≥ i. Proof. We start by proving that Pi contains at least one node labeled compress node of level ≥ i. Similarly as in the proof of Theorem 2, by the assumptions we obtain that each node of Pi is either a rake node of level ≥ i or a compress node of level ≥ i. If Pi does not contain any compress node of layer ≥ i, then Pi contains only rake nodes. By Lemma 35, this implies that there is at least one node z of Pi satisfying the following: • Node z is at distance at least T from the endpoints of Pi ; • Node z runs for at least T rounds. From these assumptions, we can reach a contradiction in the exact same way as in the proof of Claim 34. Hence, Pi contains at least one node labeled compress node of level ≥ i. As shown in the proof of Theorem 2, this implies that v is a rake node of level ≥ i + 1 or a compress node of level ≥ i. By applying Claim 36 and Claim 37 inductively, we obtain that all nodes of lower layers connected to nodes of Pk are rake nodes of level ≥ k or compress nodes of level ≥ k − 1, and hence by Lemma 35 and by the assumption on the runtime we obtain that there is at least one node of Pk labeled compress node of level ≥ k, which is a contradiction, since in a k-rake-and-compress decomposition nodes cannot be labeled compress node of level ≥ k.

Only Bounded IDs

Consider the model where nodes do not know n, but are given the promise that all IDs are integers between 1 and nc for some known c. We stress that nodes do not know anything else about n. They are only given a unique ID and a number c, together with the promise that the IDs are in {1, . . . , nc }. Since this model is more restricted than the model of Section 5, the lower bounds of that section still apply. We show that the guarantees of this setting are good enough to get the same complexities as in our lower bounds, by giving an algorithm for k-hierarchical 2 12 -coloring, that matches the complexity of Theorem 4. Theorem 7. Consider the LOCAL model where nodes have no knowledge of n, but are assigned unique IDs k−i0 1 in {1, . . . , nc }, and c is known by all nodes. Let α1 < 1c be the unique value satisfying 1 = 1−cα i0 α1 , 1 j k 1 1 cα1 where i0 := cα1 . Then, for all k > 1, k-hierarchical 2 2 -coloring can be solved in O(n ) deterministic rounds. So it seems that, for LCLs, it is already good enough to know a bound on the IDs. In fact, on a high level, our strategy is locally estimating n, based on the observed IDs. In the first phase, nodes will only continue their execution if they have observed a large enough ID. Afterwards, nodes adjust their behavior based on the results of this first phase.

6.1

The Algorithm

The algorithm consists of rules that every node checks in every round. These first two rules are generic and handle the remainder and label E. (a) All nodes in the remainder immediately output D. (b) A level 1 < j ≤ k node becomes active once all of its lower-level neighbors have decided on an output. Before that, it is inactive. 32

(c) When a node v becomes active and one of its lower-level neighbors has as output one of {B, W, E}, then v immediately outputs E. Next, is our rule for outputting consistent 2 colorings using labels B, W . Only active nodes will participate and only continuous paths of active nodes will be considered. To that end, all nodes will keep track of the maximal continuous level j path that they can see. Definition 38 (maximal active level j subpath of v). Every active level 1 < j ≤ k node keeps track of Pv , the maximal active level j subpath of v. Initially Pv = (v), and then in every round Pv tries to add the (at most) 2 level j nodes that are adjacent to Pv . It only adds a node u to Pv , if u is also active and did not output a label yet. (d) For any active node v of some level 1 ≤ j ≤ k − 1, if Pv is adjacent to a level j node that has output D, then v immediately outputs D. If on both sides of Pv , Pv either ends in a node of degree 1, or that side is adjacent to a node that outputs E, then we will aim to 2-color Pv . For this, v waits for an additional |Pv | rounds. After waiting an additional |Pv | rounds, all nodes in Pv can see all of Pv and output a consistent 2-coloring with colors B, W . In very long paths, this will result in nodes exploring their path for a very long time. To still get a fast algorithm, we have some nodes decide to output D earlier. For each 1 ≤ j < k we define a condition, such that if this condition is verified for some level j node v, then v immediately outputs D. These conditions will depend on the results from previous levels and so we keep track of the number of observed nodes. (j)

Definition 39 (size of a decline). For every node v, we store the size nv of the largest level 1 ≤ j < k decline that this node has seen so far. Initially, this value is 0 for all nodes. When a node is assigned the output D, our algorithm updates this value. The details of this are given below. The idea behind this is that if the size of the previous decline was large, then these nodes must have had a good reason to run for a long time. So as a result, also in the next phase we will be able to spend a lot of time. Before stating the conditions, we fix the behavior of nodes that are adjacent to another node that outputs D, as this is important to make sure the size of decline values propagates properly. (j)

(j)

(e) When a level j node v outputs D as a result of Rule (d), then we set nv = nu , where u is the node that did output D. We are now ready to give the decline conditions. Decline Conditions: These conditions will fix the behavior of nodes that are in very long paths, where nodes cannot see the endpoints. Only the condition for level-1 nodes will depend on the actual IDs that can be seen in the graph. For all future levels, we will use the computed sizes of the smaller level declines. (1) Condition for level 1: Let ID(i) max be the maximum ID that v has seen until round i, then v will output D, if α1 i > (ID(i) max ) . (1)

We then set nv = i. (2) Condition for level 1 < j < k: Let Pv be the maximal active subpath for v. For every node u ∈ Pv (i) (i) and 1 ≤ i < j, let nu be the maximum value of nw for any level j − 1 neighbor w of u. Then v will output D, if X |Pv |(Aj /αj ) > n(j−1) . u u∈Pv

Additionally we set n(j) v =

n(j−1) . u

u∈Pv

This finishes the description of our algorithm. Note that, because of Lemma 26, for 1 < j ≤ i0 the second condition reduces to X n(j−1) . |Pv |(Aj /αj ) = |Pv |(j·α1 )/α1 = |Pv |j > u u∈Pv

And for i0 < j < k, because of Lemma 27 the condition reduces to X n(j−1) . |Pv |(Aj /αj ) = |Pv |cα1 > u u∈Pv

We start by showing that our algorithm actually produces a correct solution. Lemma 40. The algorithm produces a correct solution to the k-hierarchical 2 21 -coloring problem. Proof. We first argue that all nodes eventually output a label and then argue that the labeling satisfies the constraints. All nodes in the remainder immediately output a label and for any node with a level, it will either decide to output a label because of one of the other rules, or Rule (d) will eventually produce a 2 coloring of all paths. Therefore, all nodes do terminate. We go through all of the conditions for a solution to be correct in order. • All nodes in the remainder give the only valid output D. • None of our rules allow for a node in level k to output D, so all nodes in level k output one of {B, W, E}. On the other hand, in the algorithm, nodes only output E if they have a lower level neighbor that outputs one of {B, W, E}. Since level-1 nodes do not have lower level neighbors, they never output E. • If a node v of any level j outputs one of B, W , then all nodes of some level j subpath Pv containing v output a consistent 2-coloring. So if v is inside the path, its neighbors neither output the same color, nor D. If instead v is an endpoint of Pv , then either v has only one same level neighbor, which is then in Pv , or the neighbor not in Pv outputs E. Both of which are fine. • The nodes that output E do so exactly based on the rule for a correct solution, so also all E outputs are correct.

With the correctness proven, what remains to show is that our algorithm achieves the desired complexity. This will be significantly more work.

6.2

Analyzing the Algorithm

We will from now on refer to this algorithm as A. To analyse A we make a connection between the execution of A and some graph gadgets. Whenever A makes some nodes output D, then such a gadget must be present. By then upper bounding the number of such gadgets, we will see that our algorithm makes sufficient progress, fast enough. The main aim of these gadgets is to capture the answer to the following question. How must a path look like for some node v to decide to output D? We want that if A is run on such a gadget, then one of its nodes will output D. We capture this property by using a simulation argument.

Definition 41 (Algorithm Simulation). For any graph G = (V, E) with some ID-Assignment ϕ : V → N to the nodes. The algorithm’s output on the pair (G, ϕ) is the (partial) output assignment σ : V → {B, W, D, E}, that is obtained when running A on G with ID-assignment ϕ. We show how we use this simulation idea in the following construction. Definition 42. A level-1 decline gadget D = (id1 , . . . , idl ) of length l is an ordered list of IDs, such that if we simulate the algorithm on a length l path P = (v1 , . . . , vl ) with ID assignments (id1 , . . . , idl ), all nodes will output label D. We call the path P of l nodes with ID assignment (id1 , . . . , idl ) the realization RD of D. Next we show that this definition is not just arbitrary, but rather that whenever some level-1 node v actually decides to output D, it is precisely because there is a decline gadget. Lemma 43. Consider any execution of the algorithm on a graph G. If a level-1 node v outputs D, then v is in a path P of G such that the ID assignment of P constitutes a level-1 decline gadget. Proof. Let P be the maximal path of level-1 nodes that contains v and i be the round in which v outputs D. Let Pv be the subpath that v has seen until round i. Then the Ids assigned to the nodes of Pv constitutes a valid level-1 decline Gadget. To see this, it is sufficient to verify that Condition (1) will also be satisfied after i rounds when running the algorithm on an isolated copy of Pv . This is true, since in an isolated copy v will see a subset of the IDs it could see in G and so if Condition (1) was satisfied in G then it is also satisfied in Pv . Since we have a level-1 path, none of the nodes in Pv ever output E. So Rule (d) can never apply, since one node between the two endpoints is already labeled D. Therefore, all nodes in the simulation will eventually output D. Since the way A behaves in the graphs gives us decline gadgets, we can also argue about the behavior of A, by giving an upper bound on the number of decline gadgets. Intuitively, we need to make sure that there are not too many small paths that decide to decline. If this were the case, then our algorithm would not make progress sufficiently fast. To show that this is not the case and our algorithm is well (enough) behaved, we give a bound on the number of decline gadgets that can exist, if we limit the number of available IDs. As a result, we also bound the number of short declining level-1 paths. Lemma 44. For any positive integer I, let DG 1 (I) be the maximum number of ID-disjoint level 1 decline gadgets that exist using IDs 1, 2, . . . , I. Then there exists some constant C, such that for any I, DG 1 (I) ≤ C · I 1−α1 . Proof. Suppose we are using IDs 1, 2, . . . , I. We will count the number of short ID assignments that can result in an output label D. The longest such path can be of length at most α1 i ≤ (ID(i) ≤ I α1 . max )

Let us define Lmax = I α1 . We will first derive an upper bound on the number pj of paths of length between Lj = L2max and Lj−1 − 1 , for any 0 ≤ j ≤ α1 log I. Since those paths have length less than Lj−1 , the j maximum ID that can be used is (1/α1 ) Lmax I (1/α1 ) Lj−1 = = (j−1)/α . 1 2j−1 2 Now assuming that all of these IDs are actually at our disposal and using that each path has length at least Lj we get (1/α1 )

pj ≤

Lmax 2j / = I 1−α1 · (j−1)/α j (j−1)/α 1 1 2 2 2 j−1 = I 1−α1 · 2 · 21−(1/α1 ) .

Lj−1 #Ids = #Ids per DG Lj

= I 1−α1 · 2 ·

2(j−1) 2(j−1)/α1

Since α1 < 1, we get that 1 − (1/α1 ) < 0. The sum of all pj can be computed as follows, because the geometric series converges. α1 log(I)

pj ≤ 2I

1−α1

j=0

α1 log(I)

21−(1/α1 )

j−1

∈ O(I 1−α1 ).

j=0

If two nodes u and v both output D and are not on the same path P , then by Lemma 43 there must also be two separate level-1 decline gadgets. The number of such decline gadgets is upper bounded by Lemma 44. Note that because Condition (1) produces smaller gadgets when using smaller IDs, we get the maximum number of such gadgets, by using the smallest possible IDs (1, . . . , n). Corollary 45. In any execution of the algorithm on an n node graph G, there are at most O(n1−α1 ) decline gadgets and hence also at most O(n1−α1 ) disjoint level-1 paths that output D as a result of Condition (1). We will now need to generalize the same notion beyond level-1 decline gadgets. Definition 46 (Decline Gadget). For all 1 < j < k, a level j decline gadget D = (P, ϕ) of length l, is a tuple consisting of the following. • P = (d1 , d2 , . . . , dl ) is a tuple of level j − 1 decline gadgets. • ϕ is an assignment of IDs to the path PR = (v1 , v2 , . . . , vl ). The realization of D is a graph RD with an ID assignment Φ. It is obtained by starting with PR , with ID assignment ϕ, and attaching to every node at position i the realisation of decline gadget di (which already have IDs assigned). Then, D is a level i decline gadget if by simulating the algorithm on (RD , Φ), all nodes in PR output D. Clearly, because of the way we defined Condition (2), the size of these gadgets will be important. Definition 47 (size of a decline gadget). For any level 1 ≤ j < k decline gadget D = (P, ϕ) we define |D| = |RD |, where RD is the realisation of D. (j)

Note that this is also exactly the value assigned to nv for all nodes on the main path of the gadget. We now want to prove a similar result as before, where if some level j node outputs D during the execution of A, then it is because there is some level j decline gadget. To make our arguments a bit cleaner we define the notion of below. Definition 48 (below). For any level j node v in G, we say that another node u is below v if and only if there exists a decreasing path of lower level nodes that connects u and v. Formally there exists Pu = (v = v0 , v1 , . . . , vl = u), such that the level of vi is greater than or equal to the level of vi+1 , for all 1 ≤ i < l. We say u is below some level j path P , if there exist some node v ∈ P , such that u is below v. Now we prove the same connection as in Lemma 43, namely that if a level j node outputs D, then it is precisely because there is a level j decline gadget. Lemma 49. For all 1 ≤ j < k, in any execution of the algorithm on a graph G, let P be a maximal level j path, such that all nodes of P output D. Then there exists a set of nodes A that are in or below P , and a level j decline Gadget D, such that |A| = RD and such that the IDs used in A and RD are the same. Proof. We prove the lemma by induction on j. The base case is already handled in Lemma 43, so suppose the lemma statement is true for j − 1, and let us show that it is true for level j. Let P be a maximal path of nodes that output D in round t. This means that for some node v and Pv ⊂ P the maximal active subpath in some round t, Condition (2) holds. (j−1)

(2) Let nu if

(j−1)

for any level j − 1 neighbor w of u. Then v will output D X |Pv |(Aj /αj ) > n(j−1) . u

be the maximum value of nw

u∈Pv

Every node u ∈ Pv has a level j − 1 neighbor (otherwise u would be level j − 1), and since u did not output E, that level j − 1 neighbor cannot output any of {B, W, E} – otherwise u would immediately have output E. So, this level j − 1 neighbor has D as output. By induction hypothesis, we get a level j − 1 decline gadget du , together with a set Au for every node in Pv = (u1 , . . . , u|Pv | ). We then construct D = ((d1 , . . . , d|Pv | ), ϕ), where ϕ just assigns the IDs of Pv . Similarly [

A = Pv ∪

Au .

u∈Pv

Clearly, |A| = |RD |, so what is left to show is that D is indeed a decline gadget. Consider the simulation of A on D. Since all of the di ’s are proper level j − 1 decline gadgets, all of the level j − 1 neighbors that are adjacent to the main path PR output D. As a result, none of the nodes in PR output E and all of them eventually become active. Note that for the path PR it is true that X X n(j−1) , n(j−1) ≥ |PR |(Aj /αj ) = |Pv |(Aj /αj ) > u u u∈PR

u∈Pv (j−1)

, are taken as the maximum values over all since PR has the exact same length as Pv and the values nu (j−1) is deneighbors. Note that for any u ∈ PR , only one of its level j − 1 neighbors is present in RD . Since nu fined as the maximum value over all neighbors, these values in PR will be at most as large as the values in Pv . Therefore, after at most t rounds of the simulation for v, Pv = PR and Condition (2) is satisfied, as argued above. So v does output D. As a result, all of the other nodes also eventually output D as a result of Rule (d), as desired. It is now clear that the behavior of our algorithm is closely intertwined with the existence of decline gadgets. Again, we have to argue and get an upper bound on the number of decline gadgets. This time however, the decline gadgets will be of higher levels. For this we will have to build larger decline gadgets from smaller ones. Let us first introduce the notion of minimal decline gadgets. Definition 50 (minimal Decline Gadget). We say that a Decline Gadget D = (P, ϕ) is minimal if and only if there does not exist a subset P ′ ⊂ P , such that D′ = (P ′ , ϕ′ ) is also a Decline Gadget. Here ϕ′ is the restriction of ϕ to PR′ . Clearly, any bound on the number of minimal decline gadgets implies a bound on the number of decline gadgets. Given a set D of decline gadgets, we can transform it into a set D′ of minimal decline gadgets, without decreasing the cardinality. To do this, just take any non-minimal gadget D = (P, ϕ) and turn it into a minimal one, by taking a subset P ′ of P , such that D′ = (P ′ , ϕ′ ) is a minimal decline gadget. Consider any level j decline gadget D = (P, ϕ). Using Definition 47 about the size of a decline gadget, we get that in the simulation of A on RD , Condition (2) reduces to X |P |(Aj /αj ) > |d|. d∈P (j−1)

Indeed, the values nv are exactly equal to |d|. We will now start proving the bound on the number of higher level decline gadgets. Note that we only aim for an asymptotic bound. In order to keep our proofs simple, we introduce a series of constants κ1 , κ2 , . . ., each hiding as many constant terms as possible, and in doing so, reducing the number of terms we have to keep track of. Claim 51 is the main reason why we want to argue about minimal decline gadgets. Claim 51. Let D = (P, ϕ) be a minimal level j-decline gadget of length L. Then there exists some constant κ2 > 0, such that for all d ∈ P it holds that |d| ≤ κ2 · L(Aj /αj )−1 .

Proof. Since D is a valid decline gadget, we get L(Aj /αj ) = |PR |(Aj /αj ) >

|d|.

d∈P

Suppose that D is still a decline gadget after having one of the d removed from P . Then the path would get 1 node shorter and the new bound would be: X (L − 1)(Aj /αj ) > |d′ |. d′ ∈P \{d}

By a first order Taylor expansion with respect to L, for some second order error term R2 (x) = O(x2 ) we get (L − 1)(Aj /αj ) = LAj /αj −

Aj (Aj /αj )−1 L + (L − 1)(Aj /αj ) · R2 (1/L). αj

So there is some constant κ2 > 0, that hides the constants (Aj and αj are constant) and the error term, such that Aj (Aj /αj )−1 LAj /αj − L + (L − 1)(Aj /αj ) · R2 (1/L) ≥ LAj /αj − κ2 L(Aj /αj )−1 . αj Now suppose that for some d ∈ P , |d| > κ2 L(Aj /αj )−1 . We get ! (L − 1)(Aj /αj ) ≥ LAj /αj − κ2 L(Aj /αj )−1 >

|d′ |

− |d| =

d′ ∈P

|d′ |.

d′ ∈P \{d}

So D′ = (P \ {d}, ϕ′ ) is valid and hence D not minimal. So, for all d ∈ P it must be that |d| ≤ κ2 L(Aj /αj )−1 . The last Claim we need for our bound on the size of a decline gadget correlates the size of a decline gadget with its length. Our lemma argues about decline gadgets of a certain length, so in order to use Claim 51 which talks about the size of gadgets, we need some glue: Claim 52. Yet again it introduces some constant – this time hidden in the big O notation. Claim 52. Any minimal level j decline gadget of size at most S has length at most O(S (αj /Aj ) ). Proof. Let D = (P, ϕ) be a minimal level j decline gadget and let κ2 be as in Claim 51. If (L − 1)(Aj /αj ) > S − κ2 L(Aj /αj )−1 , then by the same argument as in Claim 51, D cannot be minimal. So we get S − κ2 L(Aj /αj )−1 ≥ (L − 1)Aj /αj ≥ LAj /αj − κ2 L(Aj /αj )−1 ⇒ S ≥ LAj /αj ⇒ S αj /Aj ≥ L ∈ O(S αj /Aj ).

With these results in place, we can prove our bound on the number of higher level decline gadgets. Lemma 53. For any length L ∈ N, the number of minimal level j decline gadgets DG j (L) of length at most Pj L is bounded by O(L(1−Aj )/αj ), where Aj = i=1 αi . Proof. We prove the lemma by induction over j. Consider the base case. If the length of a level-1 decline gadget is at most L, then because of Condition (1), the largest ID that can be used for such a gadget is L1/α1 . So by Lemma 44, we get DG 1 (L1/α1 ) ∈ O(L(1/α1 )(1−α1 ) ) = O(L(1−A1 )/α1 ). 38

Now, let 1 < j < k and suppose that the statement of the lemma is true for j − 1. Similarly as in the proof of Lemma 44, we compute a geometric sum over the lengths. For all i, let Li = 2Li . First, we derive a bound on ni , the number of decline gadgets of length at least Li and length at most Li+1 . Any level j decline gadget D = (P, ϕ) of length at least Li consists of at least Li level j − 1 decline gadgets. By Claim 51 and since the longest gadget has length Lj+1 , all of these j − 1 decline gadgets (A /α −1) have size at most κ′2 Li+1j j for some constant κ′2 > 0. We will continue with another constant κ2 > 0 that additionally hides the +1 in the subscript. (A /αj −1)

κ′2 Li+1j

= κ′2 (Li /2)(Aj /αj −1) =

κ′2 (A /α −1) (A /α −1) = κ2 Li j j . L j j (A 2 j /αj −1) i (A /α −1)

So, what is the maximum number of minimal level j − 1 decline gadgets of size at most κ2 Li j j ? By (A /α −1) Claim 52, there exists a constant κ3 > 0, such that any level j − 1 decline gadget of size at most κ2 Li j j has length at most (αj−1 /Aj−1 ) (A /α −1) (A /α −1)(αj−1 /Aj−1 ) κ3 κ2 Li j j = κ4 Li j j . For a suitable constant κ4 . By applying our induction hypothesis, and choosing suitable κ5 , κ6 > 0, we get that the number of such level j − 1 decline gadgets is upper bounded by (1−Aj−1 )/αj−1 (A /α −1)(αj−1 /Aj−1 ) (A /α −1)(αj−1 /Aj−1 )(1−Aj−1 )/αj−1 κ5 κ4 Li j j = κ6 Li j j . Before finally resolving the big exponent, we lastly bound the number of level j decline gadget of length between Li and Li+1 , by observing that each of them requires at least Li+1 of such level j − 1 gadgets. Therefore, the total number of such level j decline gadgets is bounded by (A /αj −1)(αj−1 /Aj−1 )(1−Aj−1 )/αj−1

κ6 Li j

Li+1

(A /αj −1)(αj−1 /Aj−1 )(1−Aj−1 )(1/αj−1 )−1

= 2κ6 Li j

Now we will take care of resolving the exponent (Aj /αj − 1)(αj−1 /Aj−1 )(1/αj−1 )(1 − Aj−1 ) − 1. Case j ≤ i0 : we get

Then by Lemma 26 it holds that (Aj /αj ) = j, Aj−1 /αj−1 = j − 1 and αj = αj−1 = α1 . So

(Aj /αj − 1)(αj−1 /Aj−1 )(1/αj−1 )(1 − Aj−1 ) − 1 = (j − 1) =

1 αj−1

− (j − 1) − 1 =

1 j−1

1 αj−1

−

Aj−1 αj−1

1 1 Aj 1 −j = − = (1 − Aj ) αj αj αj αj

as desired. Case i0 < j:

Then by Lemma 30 the following hold αj = α1 c, Aj 1 αj = αj−1 , 1 − cα1 αj−1 ≤ α1 c. Aj−1

In the last inequality we don’t get an exact equality, as in the case of j − 1 = i0 we have αi0 α1 = = ⌊cα1 ⌋ ≤ cα1 . Ai 0 i0 · α 1

−1

Using these we obtain (Aj /αj − 1)(αj−1 /Aj−1 )(1/αj−1 )(1 − Aj−1 ) − 1 1 − 1 (cα1 )(1/αj−1 )(1 − Aj−1 ) − 1 ≤ cα1 = (1 − cα1 )(1/αj−1 )(1 − Aj−1 ) − 1 αj = (1/αj )(1 − Aj−1 ) − αj 1 Aj−1 αj = − − αj αj αj 1 Aj 1 = − = (1 − Aj ). αj αj αj So in either case it holds that (A /αj −1)(αj−1 /Aj−1 )(1/αj−1 )(1−Aj−1 )−1

2κ6 Li j

(1/αj )(1−Aj )

≤ 2κ6 Li

The desired bound then follows from computing a geometric sum over all i in the same way as in the proof of Lemma 44 (remember that Li = L/2i ). Lemma 54. For any 1 ≤ j < k, the maximum length of a level j-decline gadget is at most O(ncαj ) and for (j) any v, the maximum value of nv is at most ncAj . Proof. For the base case, since the largest ID is nc , Condition (1) is true for all nodes after round ncα1 . So, (1) the maximum value set for nv on any node is at most ncα1 . Suppose now that j > 1. Let D be a decline gadget (P, ϕ), of length L. For the inductive step, we use the fact that Condition (2) is satisfied together with the induction hypothesis to get X X LAj /αj > |d| ≥ O(ncAj−1 ) = O(L · ncAj−1 ). d∈P

d∈P

So we get that Condition (2) is always satisfied when L(Aj /αj )−1 ∈ O(ncAj−1 ) cAj−1 ⇒ L ∈ O n (Aj /αj )−1 and the exponent is cAj−1 cAj−1 αj cAj−1 αj = = = cαj (Aj /αj ) − 1 Aj − α j Aj−1 as desired. The bound on the size then immediately follows (Aj /αj ) (Aj /αj ) cαj (Aj /αj ) n(j) = |D| = L + L ∈ O(L ) = O (n ) = O(ncAj ). v

Using exactly the same argument, we get the following bounds when restricting to only using IDs 1, . . . , n. Note that by using the smallest possible set of n IDs, we get the largest number of level-1 decline gadgets and they also are the smallest possible, so we also get the largest number of higher level decline gadgets. Lemma 55. The maximum number of decline gadgets possible using only n IDs, is obtained by using IDs 1, . . . , n. When using only IDs 1, 2, . . . , n, for any 1 ≤ j < k, the maximum length of a level j-decline gadget (j) is at most O(nαj ) and for any v, the maximum value of nv is at most nAj .

We now use these bounds on the number of decline gadgets to argue on the progress our algorithm makes. Here, we earn the reward for all our technical work we did before, as we just need to invoke our lemmas. Lemma 56. For all 1 < j ≤ k, during the execution of A, the number of level j nodes that are adjacent to some level j − 1 node that outputs D is bounded by O(n1−Aj−1 ). Proof. By Lemma 49, for each level j − 1 neighbor u of some level j node v, it holds that if u outputs D, then there is some level j − 1 decline gadget Du . Since Du consists of a main path PDu , which has only 2 endpoints (one of which is u), only two nodes not in Du can be adjacent to Du . One of those is v. Therefore, the number of nodes adjacent to a level j − 1 decline gadget is bounded by 2 times the number of level j − 1 decline gadgets DG j−1 (L). By Lemma 55, the largest length L of a level j − 1 decline gadget is at most nαj−1 , so by Lemma 53, the number of level j nodes adjacent to a level j − 1 node that outputs D in any execution is bounded by 2 · (nαj−1 )(1−Aj−1 )/αj−1 = 2 · n(1−Aj−1 ) , as desired. The last step is to argue that all of this actually happens fast enough. However, in the definition of maximal active level j subpath of v, we potentially wait for a long time for nodes to become active. The following lemma shows that we will never wait for too long. Lemma 57. All level 1 ≤ j ≤ k nodes become active after at most (j − 1) · ncα1 rounds. Proof. We prove the statement by induction over j. The base case where all level-1 nodes are active immediately is easy. Let 1 < j ≤ k. By the induction hypothesis, all level j − 1 nodes became active after at most round number (j − 2)ncα1 . We argue that all of them choose an output after at most an additional ncα1 rounds. Consider some level j − 1 node v, which is in some maximal path P of level j − 1 nodes. Since all level j − 1 nodes are active, Pv will grow by at least 1 in every round after round (j − 2)ncα1 . If |P | < ncα1 , then either v outputs a label for some other reason, or eventually Rule (d) will apply, because v will see the endpoints of P . If instead |P | > ncα1 , then if v does not output another label we get that |Pv | > ncα1 ≥ ncαj−1 (by Lemmas 26 and 30). In the proof of Lemma 54, we argue that for nodes of level j − 1, Condition (2) is always satisfied if |Pv | ≥ ncαj−1 . Therefore, v will output D. Since v was an arbitrary level j − 1 node, after at most (j − 2)ncα1 + ncα1 = (j − 1)ncα1 rounds, all level j − 1 nodes have chosen an output, this means that all level j nodes must now be active. We can finally prove Theorem 7. Proof of Theorem 7. By Lemma 57, after at most (k − 1)ncα1 many rounds, all level k nodes become active. This means that all nodes of lower levels (and all nodes in the remainder) have chosen their outputs. What is left to show, is that these nodes do not have to spend too much time. By Lemma 56 the number of level k nodes adjacent to level k − 1 nodes that output D is at most O(n(1−Ak−1 ) ). All other level k nodes must be adjacent to lower level neighbors that output one of {B, W, E} and hence by Rule (c) these nodes output E, the moment they became active, so before or in round (k−1)ncα1 . Therefore, the number of level k nodes that did not yet output a label in round (k − 1)ncα1 is at most O(n(1−Ak−1 ) ). So the longest path of level k nodes that did not yet output a label has length at most O(n(1−Ak−1 ) ). Rule (d) will 2-color all of these level k nodes after another at most O(n(1−Ak−1 ) ) rounds. By Lemma 28, we get that n(1−Ak−1 ) ∈ O(ncα1 ). So all nodes decided on an output after at most (k − 1)ncα1 + O(ncα1 ) = O(ncα1 ) rounds. By Lemma 40 the output is correct and hence the theorem is proven.

Randomized LOCAL Model

The randomized complexity of 2-hierarchical 2 12 -coloring without knowledge of n is, surprisingly, Θ logn n .

7.1

Upper Bound

Theorem 58. There is an algorithm that solves 2-hierarchical 2 12 -coloring with locality O logn n knowledge of n.

without

Proof. We give the following algorithm: Every node in a level-1 path will mark itself with probability 21 . The path will be declined if at least one node is marked. Given a level-1 path of length l, the probability that it is declined is therefore 1 − 2−l . Further, with high probability, each level-1 path is either of length O(log n) or every node on the path sees a marked node on the path within distance O(log n). The level-1 paths can therefore be labeled within O(log n) rounds. To bound the round complexity of handling level-2 nodes, let us now compute the probability p that the algorithm needs to 2-color some fixed level-2 path of some length k. Suppose that level-1 paths of length l1 , l2 , . . . , lk are attached to this level-2 path. We get ! k k k X Y Y 1 exp −2−li = exp − (1 − 2−li ) ≤ p≤ 2li i=1 i=1 i=1 For a + b constant and a, b ∈ N, one can verify that 1/2a + 1/2b is minimal whenever a = b, if possible, or Pk |a − b| = 1 otherwise. Therefore, because i=1 li ≤ n and by letting k = 2n/(log n), we get that: k X 1 p ≤ exp − n/k 2 i=1

√ 2 n = exp − log n

By union bound, we thus get that with high probability, there is no level-2 path of length ω logn n that A needs to 2-color. The level-2 nodes can therefore be labeled in O logn n rounds. This completes the proof.

7.2

Lower Bound

Theorem 59. 2-hierarchical 2 12 -coloring requires Ω logn n locality to be solved by a randomized algorithm without knowledge of n. Proof. Let A be a randomized algorithm solving 2 12 -coloring without knowledge of n, in time o logn n . Let P be an infinite path on Z and with edges {j, j + 1} for all j ∈ Z. Let Ti′ be the random variable measuring the time for the node with ID i to stop on P. Note that because A does not know n, this Ti′ will be independent of n. If, for all n0 , there exists i such that Pr(Ti′ ≥ n0 ) ≥ 1/2, then one can take arbitrarily long subpaths of P on which the expected round complexity of A is Ω(n) and thus too large. Otherwise, there is some n0 such that for every i, Pr(Ti′ ≤ n0 ) ≥ 1/2. Now, we can build a large level-1 path P by joining up Ω(log n) disjoint subpaths of length at least 2n0 +1 of P. The center of each subpath will terminate within n0 rounds with probability at least 1/2 and therefore, the whole level-1 path P cannot be 2-colored with high probability. Recall that to solve 2 12 -coloring, a level-1 path either needs to be properly 2-colored or all nodes on the path need to output D (decline). If two nodes at distance more than 2n0 both terminate within time n0 , it is not possible to 2-color the path (we do not guarantee that the joined short segments of P together form a long segment of P. With high probability, all nodes on the level-1 path therefore have to output D. If we build Θ(n/ log n) disjoint such level-1 paths of length Θ(log n) each and join the end nodes on one side of those paths to a level-2 path, we create a level-2 path of length Ω(n/ log n) for which each node is a adjacent to a level-1 path that outputs decline. The definition of 2 12 -coloring then forces this path to be 2-colored, which takes Ω(n/ log n) rounds even with randomization.

7.3

3-hierarchical 2 12 -coloring

Definition 60 (Interesting and friendly nodes). Consider some graph G and let each node be assigned the same level as in the 3-hierarchical 2 12 -coloring problem. Assume that a partial output for 3-hierarchical 2 12 coloring is given that assigns an output label to exactly those nodes that are in level 1. We call a node of level 2 interesting if all its neighbors of level 1 output D. Similarly for a partial output for 3-hierarchical 2 21 -coloring given to all nodes in levels 1 and 2, we call a node of level 3 interesting if all its neighbors of level 1 and 2 output D. For any positive integer i and any level-2 node v ∈ V (G), let Qi (v) be the set of all level-1 nodes that can be reached from v via a path of length at most i that contains only level-1 nodes except for v. Let f : R≥1 → RS ≥0 be a monotonically increasing function. We call a path P consisting of i level-2 nodes f -friendly if | v∈V (P ) Qi (v)| < i · f (i), and f -unfriendly otherwise. Theorem 61. Let g : R≥1 → R≥0 be a monotonically increasing function satisfying g(g(x)) = log x for any real number x ≥ 2 (cf. Section 2.5.2) Then there exists a randomized Las Vegas algorithm that w.h.p. solves 3-hierarchical 2 12 -coloring with locality O(n/g(n)) without knowledge of n. Proof. Define a function f : R≥1 → R≥0 by setting f (x) := 1/3 · g(x), for each real number x ≥ 1. Consider the following algorithm A, that we provide from a global perspective. We will show later how to implement it in the distributed setting. Each node starts by computing its level. Then, each level-1 node marks itself with probability 1/2. Consider some arbitrary node v. If v is of level 1, do the following. Let Pv denote the level-1 path containing v. If Pv contains a marked node, then v outputs D; if Pv does not contain a marked node, then the nodes of Pv output a correct 2-coloring. If v is of level 2, do the following. If v is not interesting, then v outputs E. If v is interesting, then let Pv′ denote the maximal level-2 path containing v that consists of interesting nodes. If Pv′ contains an f -friendly subpath, then v outputs D. If Pv′ does not contain an f -friendly subpath, then the nodes of Pv′ output a correct 2-coloring. If v is of level 3, do the following. If v is not interesting, then v outputs E. If v is interesting, then the nodes on the maximal path of interesting nodes containing v output a correct 2-coloring. If v is of level 4 (i.e., the remaining nodes), the definition of 2 12 -coloring in Section 2.3 does not make any requirements. All nodes of level 4 can therefore output D. For the distributed implementation, each node simply does the following: in each round it sends around all the information it has received so far (and in the very first round the information it has initially) until it has received sufficient information itself to determine its output, upon which it sends its output to its neighbors and terminates. More precisely, if a node is supposed to output D or E, it will do so as soon as it has gathered sufficient information to determine that it satisfies one of the respective criteria for outputting D or E outlined in the algorithm description. Similarly, if a node is supposed to output a color, then it does so as soon as it has gathered sufficient information to determine that it satisfies one of the respective criteria and either complete knowledge of its connected component of nodes that output a color or knowledge of a path to a node in this component and of the color that this node outputs. We remark that for each connected component of nodes to be colored, a 2-coloring can be fixed via the random bits of the nodes (with probability 1), which is why “seeing” the whole component suffices for a node to determine its color. In the following, we argue that it holds w.h.p. that each node v has received the aforementioned sufficient information after O(n/f (n)) rounds. To this end, we consider the different types of nodes one by one. Note that each node can determine its level in a constant number of rounds, determining the output of level-4 nodes (which is always D) and deciding whether level-1 a node marks itself does not require any communication, which is why we ignore these two steps in the following. If v is a level-1 node, we consider two cases. If v is in a level-1 path of length at most 5 log n, then it terminates after at most 5 log n rounds. If it is in a level-1 path of length greater than 5 log n, then it has a marked node in distance at most 5 log n with probability at least 1 − 1/25 log n = 1 − 1/n5 , which implies that it terminates after at most 5 log n round with probability at least 1 − 1/n5 . Next, consider the case that v is a level-2 node. From the discussion of the level-1 nodes, we obtain by a union bound that with probability at least 1 − 1/n4 , each level-2 node knows after 5 log n + 1 rounds whether

it is interesting or not. Hence, if v is not interesting it terminates with probability at least 1 − 1/n4 after 5 log n + 1 rounds. Now consider the case that v is interesting. From the definition of an f -unfriendly path, we know that no f -unfriendly path in the input tree G can be longer than i, where i is the real number satisfying i · f (i) = n. The function f (n) is growing slowly enough such that f (n) = O(f (n/f (n))).We therefore obtain that the longest f -unfriendly path in G is of length O(n/f (n)). Hence, after each level-2 node learned the output of its level-1 neighbors, node v can determine in O(n/f (n)) rounds whether the path Pv′ from the algorithm description contains an f -friendly subpath. Note that we use here that for a level-2 node to determine whether a level-2 path of length j it is contained in is friendly takes only O(j) rounds (provided that each level-2 nodes knows the outputs of its level-1 neighbors). In conclusion, v terminates with probability at least 1 − 1/n4 after O(n/f (n) + 5 log n + 1) = O(n/f (n)) rounds. Next, consider the case that v is a level-3 node. From the discussion of the lower-level nodes, we obtain by a union bound that with probability at least 1 − 1/n3 , each level-3 node knows after O(n/f (n)) rounds whether it is interesting or not. If v is not interesting, it terminates with probability at least 1 − 1/n3 after O(n/f (n)) rounds. Now consider the case that v is interesting. Consider an arbitrary (not necessarily maximal) level-3 path P ′′ , and let v ′ be an arbitrary node on P ′′ . Since v ′ is a level-3 node it must have at least one adjacent level-2 node. Let u be such a node and let Pu′′ be the maximal level-2 path containing u (in which u is necessarily a node of degree 1). Let u′ be the node on Pu′′ that is closest to u with the property that the subpath P ∗ of Pu′′ from u to u′ contains an f -friendly subpath. Let j be the smallest positive integer such that P ∗ contains an f -friendly subpath consisting of precisely j nodes. In the following, we prove an upper bound for the probability of v ′ being an interesting node (as a function of j). Let P̂ = (u1 , . . . , uj ) be an f -friendly subpath of P ∗ consisting of precisely j nodes. For each 1 ≤ r ≤ j, let wr be a level-1 node adjacent to ur (which exists by the definition of a level-2 node) and let Pr be the maximal level-1 path containing wr and consisting of at most j nodes. For each 1 ≤ r ≤ j, the probability that ur isQinteresting is at most 1 − 1/2|V (Pr )| . This implies that the probability that all ur are interesting is at most 1≤r≤j (1 − 1/2|V (Pr )| ) (due to the independence of the events that an individual ur is interesting). Moreover, we know that X |V (Pr )| ≤ j · f (j) (5) 1≤r≤j

since P ∗ is f -friendly. Observe that 1≤r≤j (1−1/2|V (Pr )| ) is maximized under Equation (5) if |V (Pr )| = f (j) for each 1 ≤ r ≤ j. To see this, assume that this is not the case. Then in the maximizing choice for the |V (Pr )|, there Q must be two members |V (Pr1 )| and |V (Pr2 )| satisfying |V (Pr1 )| + 1 ≤ f (j) ≤ |V (Pr2 )| − 1. But then 1≤r≤j (1 − 1/2|V (Pr )| ) can be increased further by replacing |V (Pr1 )| by |V (Pr1 )| + 1 and |V (Pr2 )| by |V (Pr1 )| − 1 since 1 − 1/2|V (Pr1 )| 1 − 1/2|V (Pr2 )| < 1 − 1/2|V (Pr1 )| 2 < 1 − 1/2|V (Pr1 )|+1 ≤ 1 − 1/2|V (Pr1 )|+1 1 − 1/2|V (Pr2 )|−1 , Q

yielding a contradiction. j Hence, the probability that all ur are interesting is at most 1 − 1/2f (j) . Observe that, by the definition of u′ (and the design of A), node u outputs D only if all nodes on P ∗ output D, and the latter condition can only be satisfied if all ur output D, which in turn can only happen if all ur are interesting. Thus, u j outputs D with probability at most 1 − 1/2f (j) . It follows that v ′ is interesting with probability at most j √ 1 − 1/2f (j) . In particular, if f (j) < 1/2 · log n, then v ′ is interesting with probability at most 1 − 1/ n. Now, let n be sufficiently large, and√ consider an arbitrary path P of level-3 nodes of length precisely 2n/f (n). If there are more than 4 log n· n nodes v ′ on P for which the respective j in the above calculations satisfies f (j) < 1/2 · log n, then with probability at least 1 − 1/n4 , path P contains a node that is not interesting. √ Hence, consider the √ case that there are at most 4 log n· n such nodes v ′ on P . It follows that there are at least 2n/f (n) − 4 log n · n ≥ n/f (n) nodes on P for which the respective j in the above calculations satisfies 44

f (j) ≥ 1/2 · log n. Let V ′′ denote the set of these nodes, and consider some node v ′′ ∈ V ′′ . Let u′′ be a level-2 neighbor of v ′′ . From the above discussion (and definitions) and the definition of an f -unfriendly path, we obtain that, if v ′′ is interesting, then the number of nodes that can be reached from v ′′ via edge {v ′′ , u′′ } is at least (j ′ − 1) · f (j ′ − 1), where j ′ is the smallest positive integer j ′ satisfying f (j ′ ) ≥ 1/2 · log n. This implies that the number of nodes that can be reached from v ′′ via edge {v ′′ , u′′ } is at least f −1 (1/2 · log n) − 1 (as f (j ′ − 1) ≥ 1 for sufficiently large n). Therefore, if all nodes in V ′′ are interesting, we obtain that the input tree contains at least f −1 (1/2 · log n)·n/f (n) nodes, which implies f −1 (1/2·log n) ≤ f (n) (as the input tree contains n nodes), which in turn implies 1/2 · log n ≤ f (f (n)) ≤ f (g(n)) = 1/3 · g(g(n)) = 1/3 · log n, yielding a contradiction. Hence, in the considered case, there must be at least one node in V ′′ that is not interesting, concluding the consideration of that case. We obtain that the probability that P contains a node that is not interesting is at least 1 − 1/n4 . Since the input tree contains at most n level-3 paths of length precisely 2n/f (n), it follows by a union bound that the probability that there exists a (not necessarily maximal) level-3 path of length precisely 2n/f (n) that consists only of interesting nodes is at most 1/n3 . Now let us come back to our consideration of the interesting level-3 node v. By the above discussion, we conclude that, with probability at least 1 − 2/n3 ≥ 1 − 1/n2 (for sufficiently large n), node v terminates after O(n/f (n)) rounds. Hence, each node of the input tree terminates with probability at least 1 − 1/n2 after O(n/f (n)) rounds, which implies that, with probability at least 1 − 1/n, Algorithm A terminates after O(n/f (n)) rounds. Since g(n) = Θ(f (n)), the lemma statement follows. Theorem 62. Let g : R≥1 → R≥0 be a monotonically increasing function satisfying g(g(x)) = log x for any real number x ≥ 2. Then any a randomized Las Vegas algorithm that w.h.p. solves 3-hierarchical 2 12 -coloring requires locality Ω(n/(log n · g(n)) without knowledge of n. Proof. Let A be an arbitrary randomized Las Vegas algorithm that w.h.p. solves 3-hierarchical 2 12 -coloring (without knowledge of n). Consider first the case that there exists no positive integer c such that the probability that, at the middle node of a path of length 6c, Algorithm A terminates after at most c rounds and outputs D is at least 1/2. We claim that then, for any sufficiently large c, the probability that Algorithm A does not terminate after c rounds on a path P of length 6c is at least 1/4. To prove our claim, assume for a contradiction that A terminates on P after c rounds with probability at least 3/4. Consider two nodes v and w on P that have distance 2c + 1 from each other and greater than c from both endpoints of the path. The probability that v terminates after at most c rounds and outputs a color is at least 3/4 − 1/2 = 1/4 (as v’s c-hop view is isomorphic to the c-hop view of the middle node of P ), and the same holds for w. Since the c-hop neighborhoods of v and w are isomorphic and non-overlapping, this implies that there is some color that either node outputs with probability at least 1/8. As in any correct 2-coloring, v and w must output different colors (as they have odd distance), it follows that the output of A is incorrect with nonzero constant probability, yielding a contradiction (for sufficiently large c). Hence, the claim is true, which yields an Ω(n)-round lower bound for A. Now consider the complementary case, and let c be the smallest positive integer such that the probability that A outputs D at the middle node of a path of length 6c is at least 1/2. Fix some arbitrary integer i > 300c. For any positive integer j, let Gj denote the graph consisting of a path Pj of length 6j together with a path of length i attached at every node of Pj . Set nj := |V (Gj )|. It follows that nj = (i + 2)(6j + 1). We consider two subcases. First, consider the case that, when executing A on Gj , there exists no positive integer j such that the probability that the middle node of Pj terminates after at most j rounds and outputs D is at least 1/2. Consider some j such that 30c log nj ≤ i ≤ 30c(log nj + 1) (which exists by the definition of nj and implies nj > 300). Consider Gj . By splitting each of the 6j + 1 paths attached to the nodes of Pj into 5 log nj chunks of length at least 6c each, we see that, for each such path, the probability that it outputs D is at least 1 − 1/n5j . Hence, the probability that no node on Pj outputs E is at least 1 − 1/n4j . By an argument analogous to above, it follows that the probability that the middle node of Pj terminates after j rounds and outputs a color is smaller than 1/8 + 1/n4j (where we use that nj > 300). Thus, the probability that the middle node of Pj terminates after at most j rounds is at most 1/2 + 1/8 + 2/n4j , which implies that, on

Gj , the probability that A does not terminate after at most j rounds is greater than 1/nj . Note that, if we initially fix i to be sufficiently large, then we have j > nj /(300 log nj ). Now, consider the complementary subcase, and fix j to be the smallest positive integer such that, when executing A on Gj , the probability that the middle node of Pj terminates after at most j rounds and outputs D is at least 1/2. Moreover, let f : R≥1 → R≥0 be the function satisfying f (x) := 30c · g(x), for each real number x ≥ 1. Again, we consider two subcases (of this subcase). Consider first the case that j is such that i < f (nj ). By the definition of j, for each 1 ≤ j ′ < j, the probability that the middle node of Pj ′ terminates after at most j ′ rounds and outputs D is smaller than 1/2. Now, with an argumentation analogous to above (and using the fact that f grows faster than the log-function), we obtain that there is some j ′ satisfying 30c log nj ′ ≤ i < f (nj ′ ), such that the probability that, on Gj ′ , Algorithm A terminates after at most nj ′ /(300g(nj ′ )) rounds is greater than 1/nj ′ (if i is chosen sufficiently large initially). Finally, consider the complementary subcase, i.e., that j is such that i ≥ f (nj ). For any positive integer ℓ, let Gℓ,ℓ′ be the graph obtained as follows: start with a path Pℓ′ of length ℓ, then attach at each node of Pℓ′ a path of length ℓ′ , and finally attach at each node of each such path of length ℓ′ a path of length i. Set nℓ,ℓ′ := |V (Gℓ,ℓ′ )|. It follows that nℓ,ℓ′ = (ℓ + 1)((i + 2)(ℓ′ + 1) + 1). Now let ℓ, ℓ′ be such that 1. i ≥ 30c log nℓ,ℓ′ and 2. ℓ′ ≥ 18j log nℓ,ℓ′ . More precisely, let ℓ, ℓ′ be so that they maximize nℓ,ℓ′ with the mentioned properties. Observe that (due to the fact that, for the log-function, a multiplicative change in the argument only results in an additive change of the function value) for sufficiently large i, there exists some constant c′ that is independent of the chosen i (only requiring that i is sufficiently large and such that j exists and satisfies i ≥ f (nj )) such that 1. i ≤ c′ · 30c log nℓ,ℓ′ and 2. ℓ′ ≤ c′ · 18j log nℓ,ℓ′ . Since we also have i ≥ f (nj ), i.e., nj ≤ f −1 (i), we obtain ℓ ≥ nℓ,ℓ′ /(300c′ · 18 log nℓ,ℓ′ · f −1 (30c log nℓ,ℓ′ )). Since f (f (nℓ,ℓ′ )) ≥ f (g(nℓ,ℓ′ )) = 30c · g(g(nℓ,ℓ′ )) = 30c · log nℓ,ℓ′ , we obtain f (nℓ,ℓ′ ) ≥ f −1 (30c · log nℓ,ℓ′ ). Hence, we obtain ℓ ≥ nℓ,ℓ′ /(100c′ · 18 log nℓ,ℓ′ · f (nℓ,ℓ′ )). Observe that, with an argumentation analogous to above (and applying two more union bounds), the probability that all nodes on the attached paths of length ℓ′ output D is at least 1 − 1/n2 . Since, in this case, the nodes on the path of length ℓ need to output a proper 2-coloring, we obtain that the probability that A terminates after at most ℓ/6 rounds is smaller than 1 − 1/n. This concludes the individual considerations of all of the above cases. Using that g(n) = Θ(f (n)), we obtain that there is some positive universal constant β, such that, for any sufficiently large i, there is some graph with n > i nodes such that the probability that A terminates on this graph after at most β · n/(log n · g(n)) rounds is smaller than 1 − 1/n. This implies that there are infinitely many n such that there exists a graph G with n nodes such that A does not terminate after at most β · n/(log n · g(n)) rounds with probability larger that 1/n. This implies the claimed lower bound of Ω(n/(log n · g(n))) rounds.

References [1] Amirreza Akbari, Navid Eslami, Henrik Lievonen, Darya Melnyk, Joona Särkijärvi, and Jukka Suomela. Locality in Online, Dynamic, Sequential, and Distributed Graph Algorithms. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1–10:20, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. 46

[2] Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela. The distributed complexity of locally checkable problems on paths is decidable. In Proc. 38th ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 262–271. ACM Press, 2019. [3] Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, and Jukka Suomela. Efficient classification of locally checkable problems in regular trees. In Proc. 36th International Symposium on Distributed Computing,(DISC 2022), pages 8:1–8:19, 2022. [4] Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, and Jukka Suomela. Classification of distributed binary labeling problems. In Proc. 34th International Symposium on Distributed Computing (DISC 2020), volume 179 of LIPIcs, pages 17:1–17:17. Schloss Dagstuhl– Leibniz-Zentrum für Informatik, 2020. [5] Alkida Balliu, Sebastian Brandt, Manuela Fischer, Rustam Latypov, Yannic Maus, Dennis Olivetti, and Jara Uitto. Exponential speedup over locality in MPC with optimal memory. In 36th International Symposium on Distributed Computing, (DISC 2022), pages 9:1–9:21, 2022. [6] Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela. Lower bounds for maximal matchings and maximal independent sets. J. ACM, 68(5):39:1–39:30, 2021. [7] Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. Improved distributed lower bounds for MIS and bounded (out-)degree dominating sets in trees. In Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen, editors, PODC ’21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021, pages 283–293. ACM, 2021. [8] Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. Distributed ∆-coloring plays hideand-seek. In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 464–477. ACM, 2022. [9] Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. Distributed maximal matching and maximal independent set on hypergraphs. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 2632–2676. SIAM, 2023. [10] Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, and Gustav Schmid. Completing the node-averaged complexity landscape of lcls on trees. Technical Report 2405.01366, arXiv, 2024. Full version of this paper. [11] Alkida Balliu, Sebastian Brandt, and Dennis Olivetti. Distributed lower bounds for ruling sets. SIAM J. Comput., 51(1):70–115, 2022. [12] Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studený, Jukka Suomela, and Aleksandr Tereshchenko. Locally checkable problems in rooted trees. In Proc. 40th ACM Symposium on Principles of Distributed Computing (PODC 2021), pages 263–272, 2021. [13] Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela. How much does randomness help with locally checkable problems? In Proc. 39th ACM Symposium on Principles of Distributed Computing (PODC 2020), pages 299–308. ACM Press, 2020. [14] Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela. Almost global problems in the LOCAL model. Distributed Comput., 34(4):259–281, 2021. [15] Alkida Balliu, Keren Censor-Hillel, Yannic Maus, Dennis Olivetti, and Jukka Suomela. Locally checkable labelings with small messages. In 35th International Symposium on Distributed Computing, DISC 2021, pages 8:1–8:18, 2021. [16] Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, and Jukka Suomela. New classes of distributed time complexity. In Proc. 50th ACM Symposium on Theory of Computing (STOC 2018), pages 1307–1318. ACM Press, 2018.

[17] Alkida Balliu, Juho Hirvonen, Dennis Olivetti, and Jukka Suomela. Hardness of minimal symmetry breaking in distributed computing. In Proc. 38th ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 369–378. ACM Press, 2019. [18] Leonid Barenboim and Michael Elkin. Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition. Distributed Comput., 22(5-6):363–379, 2010. [19] Sebastian Brandt, Yi-Jun Chang, Jan Grebı́k, Christoph Grunau, Václav Rozhoň, and Zoltán Vidnyánszky. Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 29:1–29:26, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. [20] Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto. A lower bound for the distributed lovász local lemma. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 479–488. ACM, 2016. [21] Sebastian Brandt, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Patric R. J. Östergård, Christopher Purcell, Joel Rybicki, Jukka Suomela, and Przemyslaw Uznanski. LCL problems on grids. In Proc. 36th ACM Symposium on Principles of Distributed Computing (PODC 2017), pages 101–110, 2017. [22] Sebastian Brandt and Dennis Olivetti. Truly tight-in-∆ bounds for bipartite maximal matching and variants. In Proc. 39th ACM Symp. on Principles of Distributed Computing (PODC), pages 69–78, 2020. [23] Yi-Jun Chang. The complexity landscape of distributed locally checkable problems on trees. In Proc. 34th International Symposium on Distributed Computing (DISC 2020), volume 179 of LIPIcs, pages 18:1–18:17. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020. [24] Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto. Distributed edge coloring and a special case of the constructive lovász local lemma. ACM Trans. Algorithms, 16(1):8:1–8:51, 2020. [25] Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An exponential separation between randomized and deterministic complexity in the LOCAL model. SIAM J. Comput., 48(1):122–143, 2019. [26] Yi-Jun Chang and Seth Pettie. A time hierarchy theorem for the LOCAL model. SIAM J. Comput., 48(1):33–69, 2019. [27] Yi-Jun Chang, Jan Studený, and Jukka Suomela. Distributed graph problems through an automatatheoretic lens. In Proc. 28th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2021), LNCS. Springer, 2021. [28] Lawrence J. Crone and Arther C. Neuendorffer. Functional powers near a fixed point. J. of Mathematical Analysis and Applications, 132(2):520–529, 1988. [29] Christoph Grunau, Václav Rozhon, and Sebastian Brandt. The landscape of distributed complexities on trees and beyond. In Proc. 41st ACM Symposium on Principles of Distributed Computing (PODC 2022), pages 37–47, 2022. [30] Donald E. Knuth. Big omicron and big omega and big theta. SIGACT News, page 18–24, 1976. [31] Amos Korman, Jean-Sébastien Sereni, and Laurent Viennot. Toward more localized local algorithms: removing assumptions concerning global knowledge. In Proceedings of the 30th Annual ACM SIGACTSIGOPS Symposium on Principles of Distributed Computing (PODC), 2011. [32] Nathan Linial. Locality in distributed graph algorithms. SIAM J. Comput., 21(1):193–201, 1992.

[33] Arkadiusz Maciuk and Antoni Smoluk. Remarks about the square equation : functional square root of a logarithm. Mathematical Economics, 12(19):39–52, 2016. [34] Peter Bro Miltersen, N. V. Vinodchandran, and Osamu Watanabe. Super-polynomial versus halfexponential circuit size in the exponential hierarchy. In Proc. 5th Int. Conf. on Computing and Combinatorics (COCOON), pages 210–220, 1999. [35] Moni Naor and Larry J. Stockmeyer. What can be computed locally? SIAM J. Comput., 24(6):1259– 1277, 1995.

Record · ID 180633 · SHA-256 e4de8dc49c4bc7e2
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.