A Simple Construction of Locally Checkable Problems Filling the LOCAL Complexity Gaps in Graphs with Arbitrary Large Degrees

A Simple Construction of Locally Checkable Problems Filling the LOCAL Complexity Gaps in Graphs with Arbitrary Large Degrees Filippo Casagrande Gran Sasso Science Institute, Italy

Pierre Fraigniaud Institut de Recherche en Informatique Fondamentale (IRIF) CNRS and Université Paris Cité, France

arXiv:2608.18684v1 [cs.DC] 19 Aug 2026

Benjamin Jauregui - Institut de Recherche en Informatique Fondamentale, CNRS and Université Paris Cité, France - Departamento de Ingeniería Matemática, Universidad de Chile, Chile

Mikaël Rabie Institut de Recherche en Informatique Fondamentale (IRIF) CNRS and Université Paris Cité, France

Abstract We show that the complexity gaps in the round complexities of locally checkable labeling (LCL) problems are not due to the fact that solutions to LCL problems must be locally checkable, but solely to the fact that LCL problems are defined only for graphs of maximum degree upper bounded by some arbitrary yet constant value ∆. Specifically, we show that there are infinitely many locally checkable problems (i.e., problems whose solutions can be checked locally) whose round complexities belongs to the two intervals [ω(1), o(log log⋆ n)] and [ω(log⋆ n), o(log n)] whenever these problems are considered in networks with unbounded maximum degrees. This extends the previous results by Schmid (arXiv, 2026), which hold for the polynomial regime only, and by Bousquet, Feuilloley, and Pierron (OPODIS, 2025), which hold for trees only. All our upper bounds are obtained using deterministic algorithms that can be run under the port-numbering model, which is a weak variant of LOCAL, without any a priori information on the number of nodes in the network. Instead, our lower bounds apply to randomized LOCAL, and quantum LOCAL, even if nodes have identifiers in [1, n], and even if they know the exact number of nodes in the network. They even hold under randomized online LOCAL, a strong variant of the LOCAL model. Finally, our lower bounds hold even for trees. Our results are obtained using two main ingredients. The first one is the analysis of a new locally checkable problem called Increasing Degree, parameterized by a function f : N → N. Different round complexities can be obtained by tuning the function f accordingly. Our second tool is a general Translation Theorem that enables to transfer results from a given range of complexities to results for a range of lower complexities. 2012 ACM Subject Classification Theory of computation → Distributed algorithms Keywords and phrases LOCAL Model, Increasing Degree Problem, Complexity Gaps. Funding The second and fourth authors are supported by ANR Project ENEDISC (ANR-24-CE487768-01). Acknowledgements The authors are thankful to Alkida Balliu, Francesco d’Amore and Dennis Olivetti for their precious comments and advices, and to Ami Paz for preliminary discussions on the topic of this paper.

F. Casagrande, P. Fraigniaud, B. Jauregui, M. Rabie

1

Introduction

1.1

Locality and LCL Problems

The study of spatial locality in distributed computing has been mostly carried out under the so-called LOCAL model [20, 22]. Recall that this model assumes a set of n ≥ 1 processing elements connected by a network modeled as a simple connected n-node graph G = (V, E). Each node v ∈ V models a processing element provided with an identifier id(v) ∈ N, which is unique in the network. It is often assumed that the identifiers belong to an interval [0, N ] where N = poly(n) is a polynomial upper bound on the number of nodes n in the network. The bound N may be given to the nodes as an initial knowledge. Other than that, the nodes do not have information about the graph they belong to. Nodes exchange messages along the edges of the graph, which model communication links. Computation proceeds as a sequence of synchronous rounds, all nodes starting at the same round. In each round, every node performs some local computation, then sends a message to each of its neighbors in the network, and receives the messages sent by its neighbors. Under the LOCAL model, particular attention has been paid to what is known as locally checkable labeling (LCL) problems [21]. The appeal of this model lies in two features. First, it provides finite descriptions for a vast family of problems. Second, the global correctness of a solution to such a problem is the conjunction of local correctness conditions at all nodes. That is, solutions to LCL problems are easy to check, and the question is: Are they easy to compute? More formally, an LCL is described by a triple (∆, L, B) where ∆ is a positive integer, L is a finite set whose elements are called labels, and B is a finite collection of L-labeled balls of radius r in graphs of maximum degree ∆, for some integer r ≥ 0. Recall that the ball BG (v, r) centered at v and of radius r in a graph G = (V, E) is the subgraph induced by all the nodes at distance at most r from v ∈ V . A ball is L-labeled if each node w of the ball is labeled by a label ℓ(w) ∈ L. Given an LCL (∆, L, B), a distributed algorithm ALG solves the corresponding problem Π(∆, L, B) if, given any graph G = (V, E) of maximum degree ∆, ALG outputs a label in L at each node such that, for every v ∈ V , the labeled ball BG (v, r) ∈ B. Note that the specification of LCL problems is very general and enables to capture many classical graph problems such as proper vertex- or edge-coloring, maximal independent set, maximal matching, etc. Note also that one may assume input labels given to the nodes, in which case the correctness of an output labeling may depend on the given input labeling. A crucial point is that an algorithm ALG aiming at solving an LCL problem Π is designed for running specifically in graphs of maximum degree ∆, where ∆ is a fixed constant, as ALG is aiming at solving Π, which is specified only for graphs with a certain maximum degree ∆. In the LOCAL model, the round complexity of ALG is thus the maximum, taken over all n-node graphs G of maximum degree ∆, of the number of rounds executed by ALG until all nodes of G output, and the complexity of an LCL problem Π is the minimum, taken over all algorithms ALG solving Π, of the round complexity of ALG. Very many interesting facts can be stated for LCL problems, including the fact that it is undecidable whether they can be solved in a constant number of rounds [21], and the fact that the randomized complexity of an LCL problem on instances of size n is at least √ the deterministic complexity of the problem on instances of size Θ( log n) [14], which is essentially tight up to polylogarithmic factors. (This contrasts with the open question P vs. BPP in sequential computing.) Yet, one of the most striking fact about solving LCL problems in the LOCAL model is the presence of wide complexity gaps, contrasting with the

1

2

A Simple Construction of Locally Checkable Problems Filling the Complexity Gaps

Time Hierarchy Theorem for Turing machines.

1.2

Complexity Gaps

It is known [15] that no LCL problem has deterministic round complexity in the interval [ω(log⋆ n), o(log n)] where log⋆ n denotes the number of times the logarithm function should be applied to n until the result is at most 1. In other words, if an LCL problem has complexity o(log n), then it has complexity O(log⋆ n). The fact that no LCL problem can have complexity strictly between Θ(log⋆ n) and Θ(log n) came as a stunning surprise, but there is a clear explanation for this. The idea is to lie about n: many algorithms have a round complexity that depends on n only because identifiers range over poly(n). If we could instead give a virtual identifiers to every node from a range depending only on ∆, and run the algorithm on these, its complexity would no longer depend on n. Of course, in this way, many nodes will share the same virtual identifier. Coloring is used to avoid collisions while running the algorithm with this small amount of new identifiers: the algorithm do not have to find multiple nodes with the same identifier. There is a deterministic algorithm with round complexity O(log⋆ n) that solves proper O(∆2 )-coloring in graphs of maximum degree ∆ (see [20]). Applying it to the kth power graph Gk of G, where k depends on the LCL problem at hand, this gives a proper coloring of G where two nodes that share the same color are far away (with distance at least k). This enables us to run the algorithm using the colors as virtual identifiers instead of the original ones, and still producing a correct output, because the global correctness is the conjunction of local correctness conditions. Interestingly, another complexity gap pops up for lower complexities [15, 21], between Θ(log log⋆ n) and O(1). That is, if an LCL problem has deterministic complexity o(log log⋆ n), then it has constant deterministic complexity. Again, the fact that the considered graphs have maximum degree ∆ plays an important role here. Roughly, Ramsey theory enables us to show that if there is an algorithm with round-complexity o(log log⋆ n) solving an LCL problem Π, then there is an order invariant algorithm (i.e., an algorithm using only the relative order of the identifiers, not their actual values) solving Π in o(log log⋆ n) rounds. The result essentially follows from the fact that any o(log log∗ n)-round algorithm can be transformed into one whose behavior depends only on the relative order of node identifiers, rather than their numerical values. This makes it possible to iteratively compress the identifier space down to O(1) while preserving the algorithm’s behavior. Furthermore, similar complexity gaps occur for randomized algorithms, which are Monte Carlo algorithms succeeding with high probability, i.e., probablility at least 1 − O(1/n). For instance, no LCL problem has randomized round complexity in the range [ω(1), o(log log⋆ n)], or in the range [ω(log⋆ n), o(log log n)] [25]. The question addressed in this paper is the following: Do these complexity gaps persist if we relax the restriction that we must work only with graphs of bounded degree? It is worth mentioning three recent contributions that provide partial (positive and negative) answers to this question. First, it was proved by Schmid [24] that all round complexities of the form nϵ for ϵ ∈ (0, 1] exist whenever the degrees are unbounded. However, it is not known whether the complexity gaps also disappear below the polynomial regime, in particular for the two gaps [ω(1), o(log log⋆ n)] and [ω(log⋆ n), o(log n)]. Second, it was shown by Bousquet, Feuilloley and Pierron [9] that the answer is also negative if one restricts our analysis to trees. LCL problems in trees (of bounded maximum

F. Casagrande, P. Fraigniaud, B. Jauregui, M. Rabie

degree ∆) can have only the following deterministic complexity: O(1), Θ(log⋆ n), Θ(log n), and Θ(n1/k ) for all integers k ≥ 1 [18]. Bousquet et al. [9] have proved that removing the constraints on the maximum degree enables to define locally checkable problems with arbitrary round-complexities in trees. In contrast to the above two results, it was very recently shown by Piombi [23] that the complexity gaps persist even for rooted trees of unbounded degrees, whenever the locally checkable problems are defined by local Presburger monadic second-order formulas. The objective of this paper is to study whether the result in [9] extends from trees to arbitrary graphs, beyond the case of the polynomial regime studied in [24], or whether the results in [23] extends beyond local Presburger monadic second-order formulas.

1.3

Our Results

We focus on locally checkable problems, which are defined roughly as LCL problems, but where the requirement of working with graphs of maximum degree ∆ is dropped. We however keep the requirement that the global correctness of a solution is defined as the conjunction of a local correctness condition at all nodes. That is, we consider problems defined by a pair (L, φ) where L is a finite set of labels, and φ is a Boolean predicate applying to L-labeled balls of radius r in arbitrary graphs, for some integer r ≥ 0. Solving such a problem asks for labeling every node with a label in L such that the L-labeled ball of radius r centered at every node of the input graph satisfies φ. We do not enter into the details of whether the predicate φ is expressible in a certain logic (e.g., first-order logic) as we shall explicitly work with specific problems for which the predicate φ is explicit, which suffices for the purpose of this paper. In short, the take away message of this paper is that the aforementioned complexity intervals [ω(1), o(log log⋆ n)] and [ω(log⋆ n), o(log n)] are far from being empty whenever the bounded degree condition is dropped. More specifically, we establish the following set of results. For the interval [ω(log⋆ n), o(log n)], we describe problems Πf parameterized by functions f : N → N, and we show how to choose f so that to produce various locally checkable problems with many different complexities in [ω(log⋆ n), o(log n)]. In particular, we construct problems with complexities Θ(log(k) n) for all k ≥ 1, where log(k) denotes the kth iterated logarithm1 , and problems with complexities Θ(log1−ϵ n) for all ϵ ∈ (0, 1). Interestingly, we also provide a locally checkable problem with complexity Θ(log⋆ n) for which there exists an optimal algorithm that does not use identifiers. This is in contrast to LCL problems with complexity Θ(log⋆ n) whose solutions typically heavily use the node identifiers. To our knowledge, this is the first problem with complexity Θ(log⋆ n) in the port-numbering variant of the LOCAL model [2], in which nodes do not have identifiers, but the incident edges of every degree-d node are labeled from 1 to d in arbitrary order. For dealing with the interval [ω(1), o(log log⋆ n)], we construct a “translation operator” Φ that enables us to transform any problem Πf with complexity in [Ω(log⋆ n), O(log n)] into a problem ΠΦ(f ) with complexity in [Ω(log⋆ log⋆ n), O(log log⋆ n)]. The interest of this operator is that it can be iterated, to obtain a problem ΠΦ(Φ(f )) with complexity in [Ω(log⋆ log⋆ log⋆ n), O(log log⋆ log⋆ n)], and so on. Since, the function log⋆ is successively

1

For every integer k ≥ 1, the kth iterate of a function f is the function f (k) defined as f (1) = f , and f (k) = f ◦ f (k−1) for k ≥ 2 (e.g., log(2) n = log log n).

3

4

A Simple Construction of Locally Checkable Problems Filling the Complexity Gaps

Θ (log⋆ n)

Θ(1)

... Θ log♯ n

  Θ n1/2 Θ(n)

Θ(log n) ...

...

Θ log(k) n ∀k∈N

Θ log1−ϵ n ∀ϵ ∈ (0, 1)

Θ (logγ n) ∀γ > 1

  Θ n1/s ∀s > 2

Theorem 18

Theorem 9

Theorem 17

...

Figure 1 New complexities obtained directly by analyzing the complexity of specifically designed problems, tuned thanks to appropriate choices of the parameter function f . Θ(1)

Θ (log⋆ log⋆ n)

Θ (log log⋆ n) ...

Θ log♯ n

Theorem 17

...

...

Θ log(k) log⋆ n ∀k∈N

Θ log1−ϵ log⋆ n ∀ϵ ∈ (0, 1)

Theorem 13 + Corollary 14

Θ (log⋆ n)

Θ (logγ log⋆ n) ∀γ > 1

... Θ log⋆ n1/s ∀s > 2

Theorem 21 + Corollary 22

Figure 2 Complexities obtained by application of our general translation operator.

applied in this construction, all the resulting complexities remain in ω(log♯ n), where log♯ n denotes the number of times the function log⋆ must be applied to n so that to obtain a value at most 1. Nevertheless, we also design a problem with round complexity Θ(log♯ n). Figures 1 and 2 provides a compact representation of our results. It is worth pointing out the following facts resulting from our analysis.

Robust upper and lower bounds. Our lower bounds holds even for trees, while our upper bounds hold for arbitrary graphs. Moreover, our lower bounds hold even if the nodes are given identifiers in [0, n − 1], and even if n is given to the nodes as initial knowledge. Instead, our upper bounds do not assume any given bound on the number of nodes, and they hold even in the absence of identifiers. That is, our upper bounds hold in the aforementioned port-numbering variant of the LOCAL model [2]. Randomized complexity, and beyond. Our upper bounds are obtained using deterministic algorithms, but our matching lower bounds also hold for randomized algorithms. In fact, they also hold for non-signaling finitely-dependent probability distributions, which implies that they hold for quantum algorithms too, i.e., for algorithms where processing nodes can prepare quantum states, perform quantum operations on these states, and exchange qubits with their neighbors via the communication links of the network. Finally, our lower bounds also hold in the randomized online variant of the LOCAL model, one of the strongest variants of LOCAL. To sum up the above remarks, our upper bounds use deterministic algorithms, and they apply to all graphs under the port-numbering variant of the LOCAL model in absence of any information about the input graph given to the nodes. In contrast, our matching lower bounds hold for the quantum variant of the LOCAL model, as well as for the randomized online variant LOCAL, even in trees, and even if the nodes are given identifiers in [0, n − 1] in n-node trees.

F. Casagrande, P. Fraigniaud, B. Jauregui, M. Rabie

v0

v1

v2

v3

vi

5

vi+1

vk

Figure 3 A path v0 , . . . , vk with increasing “leaf degrees”, i.e., with ♯leaf(vi+1 ) ≥ f (♯leaf(vi )). The small black nodes are leaves.

1.4

Our Techniques

It may seem at a first glance that locally checkable problems with complexities in the empty gaps of the complexity landscape of LCL problems can easily be obtained from LCL problems whose complexities are functions of ∆ and n. One typical example is sinkless orientation, whose complexity is known to be Θ(log∆ n) [11, 17]. One can define a problem, called threshold sinkless orientation, with complexity t(n) by setting a threshold degree ∆0 = nO(1/t(n)) . This problem consists of solving sinkless orientation whenever the graph has maximum degree ∆ ≤ ∆0 , and doing nothing otherwise. However, this approach suffers from several weaknesses. First, for solving the problem, the nodes need to be given the maximum degree ∆ of the input graph, whereas the LOCAL model assumes that the sole global information given to the nodes is a polynomial upper bound on the number of nodes. Second, the definition of the problem depends on the number of nodes in the input network, whereas it is desirable that the problem definition (whether it be LCL problems or locally checkable problems) be independent of the size of the input. Last, but not least, the lower bound for the chosen problem (e.g., sinkless orientation) generally holds only for deterministic algorithms, sometimes to randomized algorithms, but not to quantum algorithms (not to speak about non-signaling finitely-dependent distribution). Instead, the approach used in this paper yields problems whose quantum complexities can be lower bounded, which allows us not only to fill up complexity gaps for deterministic algorithms, but also for randomized algorithms. The following problem, called Increasing Degree, and denoted by Πf , plays a major role for obtaining our results. It is parameterized by a function f : N → N satisfying f (x) > x for every x ∈ N. Recall that, in a simple graph G = (V, E), a leaf is a node of degree 1, i.e., a node v such that deg(v) = 1, where deg(v) = |N (v)| with N (v) = {w ∈ V | {v, w} ∈ E}. We denote by ♯leaf(v) the number of leaves adjacent to v. ▶ Definition 1. Given f : N → N, we say that a node v of G is balanced (with respect to f ) if it is a leaf, or all its neighbors are adjacent to less than f (♯leaf(v)) leaves, i.e., if

deg(v) = 1 ∨ ∀w ∈ N (v), ♯leaf(w) < f (♯leaf(v)) . A node v which is not balanced is unbalanced. For every unbalanced node v, every neighbor w ∈ N (v) satisfying ♯leaf(w) ≥ f (♯leaf(v)) is said to be a heavy of v (with respect to f ). A balanced node v may thus have neighbors w with ♯leaf(w) > ♯leaf(v), yet the number of leaves adjacent to w cannot be too large, as it must be less than f (♯leaf(v)). In the Increasing Degree problem Πf , for a fixed function f , each node v receives a value ℓin (v) ∈ {0, 1} as input, and must produce an output ℓout (v) ∈ {0, 1}. The output of a balanced node must simply be equal to its input, whereas the output of an unbalanced node v must be equal to the output of one of its heavy neighbors w.

6

A Simple Construction of Locally Checkable Problems Filling the Complexity Gaps

The difficulty for an unbalanced node v to produce its output is that its heavy neighbor w may be unbalanced too, with heavy neighbor w′ which may also be unbalanced, and so on, until a balanced node is found. This chain of heavy neighbors (see Figure 3) may force v to query nodes at long distance from it for producing its output. Formally, the Increasing Degree problem is described as follows: Increasing Degree Problem Πf = (L, φf ) Labeling at node v: ℓ(v) = (ℓin (v), ℓout (v)) ∈ L = {0, 1} × {0, 1} = Lin × Lout Correctness predicate φf at node v:   φf (v) = (v balanced) ∧ (ℓout (v) = ℓin (v)) ∨ 
 (v unbalanced) ∧ ∃w ∈ N (v) : (w heavy w.r.t. v) ∧ (ℓout (v) = ℓout (w)) An algorithm solves the Increasing Degree Problem Πf in a graph G = (V, E) if, given any input assignment ℓin : V → {0, 1} to the nodes (i.e., node v receives ℓin (v) as input), every node v outputs ℓout (v) such that the predicate φf is satisfied at all nodes. Remark. Any solution ℓ : V → {0, 1} × {0, 1} to an Increasing Degree Problem Πf is locally checkable at every node v. Indeed, assuming every node initially knows its degree, whether φf (v) is satisfied can be decided based solely on information available in the distance-2 neighborhood of v: At the first round, every node v computes the number of leaves adjacent to it, which is sufficient to check φf (v) using one additional round. Note that, in trees, one can define a variant of the Increasing Degree problem in which one plays directly with the degrees, and not with the number of leaves. In this case, checking φf (v) can be done in a single round. On the other hand, computing the output label at a node may require a large number of rounds, depending on f . Intuitively, the reason for this is that there might exist a long path v0 , v1 , . . . in the input graph G, where, for every i ≥ 1, vi is a heavy neighbor of vi−1 (see Figure 3 for an illustration). As a consequence, the output ℓout (v0 ) may depend on the input label ℓin (vk ) of a node vk at large distance k from v0 . Yet, if di = ♯leaf(vi ), we have that di ≥ f (i) (d0 ) where f (i) denotes the ith iterate of f , and this value cannot exceed n, which in turn upper bounds the value of k as a function of n. Roughly, by picking the smallest value for d0 = ♯leaf(v0 ), i.e., d0 = 0, we show that the complexity of Πf is k n o X t(n) = max k ≥ 0 | (k + 1) + f (i) (0) ≤ n

(1)

i=1

whose value is represented by the length of the path v0 , . . . vk in Figure 3. The difficulty of the analysis thus comes from the difficulty of solving Equation (1) for a given function f . For some specific functions f , this is straightforward, but this is not systematic. Moreover, obtaining problems Πf with very small round complexities requires to choose rapidly growing functions f , for which solving this equation is non trivial. This holds even if, for rapidly growing functions f , Equation (1) can be simplified into n o t(n) ≃ max k ≥ 0 | f (k) (0) ≤ n . (2)

F. Casagrande, P. Fraigniaud, B. Jauregui, M. Rabie

Again, solving Equation (2) might be straightforward for some specific functions, but not for the vast majority of them. This is where our aforementioned “translation operator” Φ plays an important role for providing a systematic way of generalizing solutions for some functions f to solutions for functions growing much faster than f . Given any Increasing Degree problem Πf with complexity tf (n) ≤ O(log n), the operator Φ produces a new version of the Increasing Degree problem, ΠΦ(f ) , with exponentially smaller complexity. More specifically, this operator transforms f into the function Φ(f ) where  2 .. Φ(f )(x) = 22 . f (log⋆ x) times from which it follows that ΠΦ(f ) has complexity
tΦ(f ) (n) = Θ tf (log⋆ n) . Such technique plays an important role: once some version of the Increasing Degree problem with complexities belonging to the interval [ω(log⋆ n, ), o(log n)] have been found, we are able to find some other correlated problem with complexities in [ω(1), o(log log⋆ n)]. Note that the two intervals [ω(1), o(log log⋆ n)] and [ω(log⋆ n, ), o(log n)] are the well-known gaps where no complexity can be found for any general LCL problem (in the bounded degree setting).

1.5

Related Work

An excellent entry to the research line studying the landscape of complexity of LCL problems in the LOCAL model is [25]. This landscape has also been studied for specific sub-classes of graphs such as paths, cycles, and toroidal grids [12], paths with inputs [3], trees [13, 18], and rooted trees [5]. It is worth mentioning that another form of complexity landscape, focusing on the size of the certificates required to certify predicates on paths and cycles, has recently been studied in [10]. To show the existence of problems with complexities belonging to some specific subinterval of [0, n − 1], a common technique is to generate (artificial) problems with specific complexities. A large number of reachable complexities between Ω(log log∗ n) and o(log n), Θ(1) n as well as of the form nΘ(1) and 2log have been exhibited in [6, 8]. In the case of trees, it was proved [15] that there are problems with complexities n1/k , for any integer k ≥ 2, but that there is a complexity gap in the interval [ω(log n), o(poly(n))]. All these constructions assume, for the upper bound on the complexity of each considered problem, that the nodes are given the exact value n of the size of the network. It was proved [4] that the existing complexities in trees may vary depending on the degree of knowledge about n, and that randomization helps in absence of any knowledge, which is not the case when n is known. We also refer to [16] about the impact of the knowledge of n on the ability to perform efficient distributed computation. In terms of techniques, a mechanism forcing nodes to transmit information along a path of length k to get a problem with complexity k has already been used (see, e.g., [3, 7]). We complete this brief survey of the related literature by pointing out that the complexity of locally checkable problems when the constraint imposing the maximum degree to be bounded is removed has already been recently studied in [9, 24]: In [24], the existence of locally checkable problems with round complexities Θ(nα ), for any α ∈ [0, 1], has been established. This result is obtained using known facts about algebraic partitions of integers. Our results for the polynomial range reuse some of these ingredients for constructing problems with finer round complexities Θ(nα logβ n), in complement to our main results regarding the sub-polynomial regime.

7

8

A Simple Construction of Locally Checkable Problems Filling the Complexity Gaps

The construction in [9] enables to obtain locally checkable problems with arbitrary round-complexities, whenever one restricts the analysis to trees. The issue of extending their results from trees to arbitrary graphs was explicitly left open in [9]. Moreover, as underlined in [24], “the result in [9] offers little insight into why locally checkable problems can behave so erratically whenever the degree constraint is relaxed”, and “it is unclear which aspects are responsible for the collapse of structure in the complexity landscape for these problems”. Instead, our problems are explicit, simple to describe, and their solutions can be checked locally in a single round. Finally, as mentioned before, it is known [23] that the complexity gaps persist even for rooted trees of unbounded degrees, for the wide class of locally checkable problems defined by local Presburger monadic second-order formulas. In the Increasing Degree problems, we use functions such as x 7→ x2 , which cannot be implemented in Persburger arithmetic.

1.6

Organization of the paper

Section 2 shows the existence of a locally checkable problem with complexity Θ(log log n), whereas it is known that no LCL problem can have such complexity. It also shows the √ existence of an Increasing Degree problem with complexity Θ( n). This latter complexity was known the be achievable by LCL problems, but Section 2 is also the opportunity to introduce the reader with the Increasing Degree problem at the core of our contribution. Section 3 considers the sublogarithmic gap [ω(log⋆ n), o(log n)] that we refer to as the Chang-Pettie Interval [15], whereas Section 4 consider the gap [ω(1), o(log log∗ n)] that we refer to as the Ramsey interval [21]. Section 5 is partially dedicated to filling up the known gaps in the complexity of LCL problems in trees, in both polynomial and polylogarithmic regimes, using a simple variant of the Increasing Degree Problem. Section 6 focuses on √ 1 complexities above Ω( n), providing refined complexities of the form Θ(n 2 +ϵ logα n). Finally, Section 7 concludes the paper with open problems.

2

√ Problems with Respective Complexities Θ(log log n) and Θ( n)

This section can be used as a warm-up, but it already includes an important result, namely the existence of a locally checkable problem with complexity Θ(log log n), whereas it is known that no LCL problem has complexities in the interval [ω(log⋆ n), o(log n)]. This section also √ shows the existence of a locally checkable problem with complexity Θ( n). The existence of such a problem was already known, even for LCL problems, and even if one restricts attention to trees. However, our construction is new, and it provides an introduction to the more sophisticated construction introduced later in the paper. Moreover, our construction does not use any knowledge about the value of n, as opposed to the previous construction [15], about which it has been recently proven in [4] that without this knowledge, the complexity changes.

2.1

A Locally Checkable Problem with Complexity Θ(log log n)

▶ Theorem 2. There exists a locally checkable problem with round complexity Θ(log log n) in n-node graphs. The lower bound Ω(log log n) also holds for trees. Proof. We show that the Increasing Degree Problem Πf with f (x) = x2 satisfies the

F. Casagrande, P. Fraigniaud, B. Jauregui, M. Rabie

statement of the theorem. More precisely, let f : N → N defined as  if x = 0  1 f (x) = 2 if x = 1  2 x otherwise

9

(3)

in order to guarantee that f (x) > x for every x. To establish the upper bound, we first show the following basic claim. ▷ Claim 3. For any path P = (v0 , . . . , vk ), if v0 , . . . , vk−1 are unbalanced nodes and, for every i ∈ {1, . . . , k}, vi is a heavy neighbor of vi−1 with respect to f , then P is of length k = O(log log n). To establish the claim, let di = ♯leaf(vi ) for every i ∈ {0, . . . , k}. For every i ≥ 1, since vi i+1 is a heavy neighbor of vi−1 , we have di ≥ d2i−1 , and thus di ≥ d20 . (Eq. (3) guarantees that if d0 ∈ {0, 1}, then d1 ≥ 2, so the amount of leaf neighbors increases traveling the path even for these cases.) As a consequence, the total number of nodes in P plus the leaves adjacent these nodes is at least (k + 1) +

k X

 k di = Ω 22 .

i=0

Since this number cannot exceed n in n-node graphs, we get that the length k of the path cannot exceed O(log log n), as claimed. The Algorithm. Our algorithm (see Algorithm 1) does not require to know the aforementioned bound O(log log n). Moreover, it does not require node identifiers, nor any information of the number of nodes in the network, and it can be implemented in the port-numbering version of the LOCAL model. It proceeds as follows. After having collected the degrees deg(w) and the leaf-degree ♯leaf(w) of each of its neighbors w, every node v knows whether it is balanced or unbalanced, and, in the latter case, which of its neighbors are heavy. The algorithm then proceeds differently depending on whether v is balanced or not. If v is balanced, then it merely sends its input ℓin (v) to all its neighbors, sets its output ℓout (v) to ℓin (v), and terminate. If v is unbalanced, then it waits to receive a value x ∈ {0, 1} from one of its heavy neighbors. When it eventually receives such a value x, it forwards it to all its neighbors, and terminates with output ℓout (v) = x. Correctness. Note first that Algorithm 1 guarantees that every balanced node v outputs its input, as desired. To show that every unbalanced node v outputs correctly, let us consider the general scenario of a chain v0 , v1 , . . . , vk for k ≥ 1, satisfying that (1) v0 = v, (2) for every i ∈ {0, . . . , k − 1}, node vi is unbalanced, and vi+1 is a heavy neighbor of vi , and (3) vk is balanced. Let us show by induction, that node vi terminates correctly at most k − i rounds after vk terminated. The result holds for vk−1 as it receives the value x = ℓout (vk ) directly from vk at the round at which vk terminates. Assuming the result holds for 0 ≤ i < k, let us show that it holds for i − 1. Let ti ≤ i be the number of rounds elapsed between vk and vi terminate. When vi−1 terminates, it is because it has received a value x ∈ {0, 1} from one of its heavy neighbors. This occurs at most ti + 1 rounds after vk terminated, as vi sends its output value x to vi−1 before terminating. Therefore, ti−1 ≤ ti + 1 ≤ k − (i − 1), as claimed. It follows that v = v0 terminates at most k rounds after vk terminated.

10

A Simple Construction of Locally Checkable Problems Filling the Complexity Gaps

Algorithm 1 Solving the Increasing Degree Problem Πf : Code of node v with input ℓin (v) ∈ {0, 1} 1: send deg(v) to neighbors, and receive deg(w) from every neighbor w 2: send ♯leaf(v) to neighbors, and receive ♯leaf(w) from every neighbor w 3: if v is balanced then

send ℓin (v) to all neighbors ℓout (v) ← ℓin (v) ▷ balanced nodes set their outputs and terminate 6: else 7: repeat 8: receive messages (if any) from neighbors 9: until a value x ∈ {0, 1} is received from an heavy neighbor 10: send x to all neighbors 11: ℓout (v) ← x ▷ unbalanced nodes set their outputs and terminate 12: end if 4:

5:

Upper Bound. Since we have proved in Claim 3 that no paths v0 , v1 , . . . where vi is an heavy neighbor of vi−1 for all i ≥ 1 can have a length k exceeding O(log log n), we get that Algorithm 1 completes in O(log log n) rounds, as claimed. Lower Bound. We now show that the Increasing Degree Problem Πf has worst-case round complexity Ω(log log n), even in trees. For this purpose, let us consider the tree T containing a path P = (v0 , v1 , . . . , vk ), with k = Ω(log log n), which we refer to as the spine of T . Node v0 has one neighbor that is a leaf, and, for every i ∈ {1, . . . , k − 1}, node vi is connected to i−1 leaves. By construction, all nodes v0 , . . . , vk−1 of the spine are unbalanced, f (i) (1) = 22 and only vk is balanced. The lower bound merely follows from an indistinguishability argument: if node v0 performs less than k rounds, and outputs 0 in an instance where ℓin (vk ) = 0, then it also outputs 0 when ℓin (vk ) = 1. This completes the proof. ◀ Observe that, by the same arguments as in the proof of Theorem 2, it can be derived that the Increasing Degree problem Πf with f (x) = x2 has complexity Θ(log log ∆) in graphs with maximum degree ∆, hence constant round complexity whenever ∆ = O(1), as for LCL problems. In fact, this is general for the Increasing Degree Problem Πf , for all increasing function f . Indeed, in graphs of maximum degree ∆, the length of a chain of heavy neighbors cannot exceed a constant value t = t(f, ∆) uniquely defined by f and ∆. Therefore, Algorithm 1 applied with f will have complexity at most t = O(1) in graphs of bounded maximum degree.

2.2

On Stronger Variants of LOCAL

The lower bound in the proof of Theorem 2 use simple indistinguishability arguments. As such, they also apply to randomized LOCAL algorithms, and to non-signaling algorithms, which include quantum LOCAL algorithms. This holds for all the lower bound proofs in the remainder of the paper. The case of the randomized online LOCAL algorithm however needs some more care. Among the several well-studied variants of LOCAL, the randomized online LOCAL model is indeed the most powerful one. That is, any lower bound that holds in this latter model also holds in any other variants of LOCAL such as randomized-LOCAL, quantum-LOCAL or SLOCAL [1]. Recall that, in the online LOCAL model, the nodes of the input graph G are processed sequentially with respect to an order σ = (v1 , v2 , . . . , vn ) arbitrarily chosen by an adversary.

F. Casagrande, P. Fraigniaud, B. Jauregui, M. Rabie

An algorithm A for this model acts as an online algorithm, keeping track of the part of the graph discovered so far. Specifically, at each step i ≥ 1, A updates its memory to include the portion of the graph G within distance d ≥ 0 of the node vi — referred to the locality of A. A has then to produce an irrevocable output label ℓout (vi ) for node vi , which depends of the problem at hand (such a label may be a color, a Boolean indicating whether the node belongs to a maximal independent set, etc.). The algorithm then proceeds to the next step. A may be deterministic or randomized. The proof of Theorem 2 can be slightly modified to establish the following. ▶ Corollary 4. There exists a locally checkable problem with round complexity Θ(log log n) in n-node graphs, where the lower bound Ω(log log n) also holds for trees under the randomized online LOCAL model. Proof. We consider the same problem Πf as in the proof of Theorem 2, and thus the upper bound follows from that theorem. For the lower bound, we show than no randomized online LOCAL algorithms with locality o(log log n) can solve Πf . We use the same tree T which contains the path P = (v0 , ..., vk ), called the spine of T , with k = Ω(log log n) (see Figure 3). For the purpose of contradiction, let A be a randomized online LOCAL algorithm solveing Πf with locality k/3. Let then σ = (vk , v0 , v1 , . . . ) be the sequential order which the adversary selects the nodes. Let us assume that the input label of vk is ℓin (vk ) = 0, and that ℓin (vk/2 ) = 1. Due to the structure of T , v0 has to know the output of vk to produce its own output. After discovering vk and v0 , the adversary can change T into T ′ , which only differs from T in the existence of an extra node w in the spine P inserted between vk/2 and vk/2+1 . Since the locality of A is k/3 the algorithm cannot distinguish T from T ′ after having discovered vk and v0 only. The presence of w however makes vk/2 a balanced node in T ′ . It follows that v0 has to output ℓout (v0 ) = 1 in T ′ , in contrast to the output ℓout (v0 ) = 0 in T . Since both T and T ′ are legal input configuration after two steps of A, there is no way for algorithm to produce a correct output label for v0 . ◀ Remark. The proof of Corollary 4 is not specific of the complexity Θ(log log n), and it actually holds throughout the paper, for all results using an Increasing Degree problem Πf for establishing some new complexity, independently of the choice of the function f . √ In particular, it also holds for the Increasing Degree problem Πf with complexity Θ( n) described in the next section.

2.3

√ A Locally Checkable Problem with Complexity Θ( n)

√ ▶ Theorem 5. There exists a locally checkable problem with round complexity Θ( n) in √ n-node graphs. The lower bound Ω( n) also holds for trees. Proof. We show that the Increasing Degree Problem Πf with f (x) = x + 1 satisfies the statement of the theorem. We proceed as in the proof of Theorem 2, by upper bounding the length of any chain of heavy neighbors. Let P = (v0 , . . . , vk ) be a simple path such that, for every i ∈ {0, . . . , k − 1}, vi is unbalanced, and vi+1 is an heavy neighbor of vi . If di = ♯leaf(vi ), then we have that the path P together with the leaves attached to it amount Pk for at least i=0 di nodes. Since di ≥ di−1 + 1 for every i ≥ 1, and d0 ≥ 0, we get that Pk √ even this sum is at least i=1 i = 12 k(k − 1), and thus k = O( n). We can then reuse Algorithm ?? with f (x) = x + 1 instead of f (x) = x2 , and conclude that the complexity of Πf √ √ is O( n), as claimed. The lower bound Ω( n) for trees follows from the same construction

11

12

A Simple Construction of Locally Checkable Problems Filling the Complexity Gaps

as for the lower bound proof in Theorem 2. The constructed spine v0 , . . . , vk has length √ k = Ω( n), and the lower bound follows. ◀

3

Complexities in the Chang-Pettie Interval

√ The approach used to derive the Θ(log log n) and Θ( n) complexity bounds in Section 2 consists of defining a suitable function f : N → N for which the corresponding Increasing Degree Problem Πf has the desired round complexity. In this section, we show how to apply this technique to get infinitely many complexity values in the Chang-Pettie interval [ω(log⋆ n, o(log n)]. To simplify the analysis of Equation (1), which will play a major role in the main results of this section, we make the following assumption. ▶ Remark 6. Throughout the paper, whenever considering a function f : N → N, we assume that f (0) = 1 and f (1) = 2 are fixed, and, for x ≥ 2, the function is defined according to a proper expression, as it was done for the function f (x) = x2 in Eq. (3). Given a function f : N → N with f (x) > x for every x, and a graph G, recall that a heavy path in G is a path P = (v0 , . . . , vk ) such that vk is balanced, every node in V (P ) ∖ vk is unbalanced, and, for every i ≥ 1, the node vi is an heavy neighbor of vi−1 . The round complexity of the Increasing Problem Πf is the length of the longest heavy path. (This directly follows from the design of the generic Algorithm ??, which provides the upper bound, and the generic construction in the proof of Theorem 2, which provides the lower bound.) We thus state the following for further references. ▶ Observation 7. The round complexity Tf (n) of the Increasing Problem Πf satisfies k n o X Tf (n) = max k ≥ 0 | (k + 1) + f (j) (0) ≤ n . j=1

Furthermore, when f grows rapidly, the expression for Tf (n) in Observation 7 is dominated by the largest term, so we can observe what follows. ▶ Observation 8. If f (x) ≥ 2x for every x ∈ N, then Tf (n) ∈ Θ(max{k ≥ 0 | f (k) (0) ≤ n}). The main result in this section is the following. ▶ Theorem 9. There exist locally checkable problems with the following round   complexities in ⋆ ϵ (k) n-node graphs: Θ (log n), Θ (log n) for every ϵ ∈ (0, 1), and Θ log n for every integer k ≥ 1. In all cases, the lower bounds also hold for trees. The rest of the section is dedicated to the proof of Theorem 9. To exhibit Increasing Degree problem with complexity Θ(log⋆ n), let us consider the function f : N → N defined as f (x) = 2x for every x ≥ 0. Thanks to Observations 7 and 8 we can focus on determining the maximum k such that f (k) (0) ≤ n. We have  2 . (k) .. f (0) = 22 k − 2 times Therefore, f (k) (0) ≤ n whenever k ∈ O(log⋆ n), and the largest k satisfying this inequality is in Θ(log⋆ n).

F. Casagrande, P. Fraigniaud, B. Jauregui, M. Rabie

13

Let ϵ ∈ (0, 1). To exhibit a problem with complexity Θ log1−ϵ n , let us consider the function f : N → N defined as ϵ

f (x) = x · 2log x for x ≥ 2, with the usual convention that f (0) = 1, and f (1) = 2. Again, we can focus on determining the maximum k such that f (k) (0) ≤ n. ▷ Claim 10. For any k, x ∈ N with x ≥ 2, we have f (k) (x) = 2yk (x) , where y1 (x) = log x + logε x and yk+1 (x) = yk (x) + ykε (x) for all k ≥ 1. Proof. By induction on k. We have ε

ε

ε

f (1) (n) = n · 2log (n) = 2log n · 2log (n) = 2log n+log (n) = 2y1 . Moreover, assuming that f (k) (n) = 2yk (n) , we have that ε

f (k+1) (n) = f (f k (n)) = f (2yk (n) ) = 2yk (n) · 2log 2

yk (n)

ε

= 2yk (n)+yk (n) = 2yk+1 (n) ◀

as claimed.

▷ Claim 11. For every integer x ≥ 2, the sequence (yk (x))k≥0 defined in Claim 10 satisfies
1/(1−ε) yk (x) ∈ Θ k . Proof. Let g(x) = x1−ε . By the Mean Value Theorem, for every a < b there exists a constant β ∈ (a, b) such that f (b) − f (a) = f ′ (β)(b − a) where f ′ (β) = (1 − ε)x−ε . Since x is fixed, we denote yk (x) simply as yk . We get that 1−ε yk1−ε − yk−1 = g(yk ) − g(yk−1 )

since yk−1 ≥ yk

= (1 − ε)βk−ε (yk − yk−1 ) ε = (1 − ε)βk−ε yk−1  ε yk−1 = (1 − ε) ·

for some βk ∈ (yk−1 , yk ) by def. of yk

βk

We use the following result to continue. ▷ Claim 12. There exists two constants C1 , C2 ∈ R≥0 such that, for every k ∈ N, and every βk ∈ (yk−1 , yk ), we have C1 ≤ (yk−1 /βk )ε ≤ C2 . Proof. Let k ∈ N and βk ∈ (yk−1 , yk ). We have yk−1 /βk ≤ yk−1 /yk−1 = 1. Therefore, by using C1 = 1, we prove the lower bound. Analogously, we have that yk−1 /βk ≥ yk−1 /yk . ε Since yk = yk−1 + yk−1 , we get yk−1 yk−1 yk−1 1 ≥ = = ε−1 ε−1 . ε βk yk−1 + yk−1 yk−1 (1 + yk−1 ) 1 + yk−1 ε−1 Since yk−1 ≥ y1 as {yk }k∈N is increasing, and since ϵ − 1 ≤ 0, we get that yk−1 ≤ y1ε−1 , from which we derive that

1 1 . ε−1 ≥ 1 + yk−1 1 + y0ε−1  Therefore, by taking C2 =

1 1 + y0ε−1

−ϵ we obtain the desired upper bound.

◀

14

A Simple Construction of Locally Checkable Problems Filling the Complexity Gaps

Going back to the proof of Claim 11, we have that ε  yk−1 1−ε . yk1−ε − yk−1 = (1 − ε) · βk 1−ε By Claim 12, we then obtain that Cˆ1 ≤ yk1−ε −yk−1 ≤ Cˆ2 with Cˆ1 = (1−ε) and Cˆ2 = (1−ε)C2 . ˆ ˆ Since the constants C1 and C2 are independent of k, by using k times these last inequalities we get that Cˆ1 · k + y11−ε ≤ yk1−ε ≤ Cˆ2 · k + y11−ε . Finally, since y11−ε is constant for a fixed x, we eventually get that C1 ′ · k
1/(1−ε) ≤ yk ≤ C2 ′ · k 1/(1−ε) for proper constants C1′ and C2′ . It follows that yk ∈ Θ k 1/(1−ε) , completing the proof of Claim 11. ◀

By Claim 10, we get that 2ykn (2) ≤ n, and by Claim 11 this later inequality is equivalent 1/(1−ϵ) to 2k ≤ n, from which we
conclude that if k is the maximum integer satisfying this inequality, then k ∈ Θ log1−ϵ n , concluding the proof for the complexities Θ(log1−ϵ n). We finally exhibit a problem with complexity Θ(log(k) n) for every integer k ≥ 1. The case k = 1 is known (and can be also obtained by considering Πf with f (x) = 2x), and the case k = 2 was established in Theorem 2. Let k ≥ 3, and let us consider the function f : N → N defined as f (0) = 1, f (1) = 2 and, for all x ≥ 2,

f (x) =

(log(k−2) x)

22

2

2

)

2 ··

k − 2 twos

That is, f (x) is a tower of k − 2 2’s, with the topmost exponent equal to Again, we use Observation 8, we look for the largest k such that f in j ≥ 1, we get that, for every integer x ≥ 2,

f (j) (x) =

22

· 2·

(log(k−2) x) 2

2j

(k)



log(k−2) x

2

.

(2) ≤ n. By induction

) k − 2 twos

It follows that the largest k satisfies k ∈ Θ(log(k) n). This completes the proof of Theorem 9.

4

Complexities in the Ramsey Interval

Any version of the Increasing Degree problem Πf can be associated with a round complexity Tf (n) given by Observation 7. In the previous section, we showed how it is possible to find specific functions f to exhibit many locally checkable problems with different asymptotic complexities in the Chang-Pettie interval [Ω(log⋆ n), O(log n)]. We now exhibit a systematic way to transform such functions f to functions g whose associated Increasing Degree problem Πg have different asymptotic complexities in [Ω(log⋆ log⋆ n), O(log⋆ n)], i.e., in the Ramsey interval. ▶ Theorem 13. Let Πf be the Increasing Degree problem associated to a function f satisfying f (x) ≥ 2x for all x ∈ N, with complexity Tf (n). There exists a function g such that the associated Increasing Degree problem Πg has complexity Tg (n) = Θ(Tf (log⋆ n)). Proof. The function f is mapped to the function g : N → N satisfying  2 .. g(x) = 22 . f (log⋆ x) times.

F. Casagrande, P. Fraigniaud, B. Jauregui, M. Rabie

Note that log⋆ (g(x)) = f (log⋆ x). Then, composing the function g with itself k times for any k ∈ N, we have that  2 .. g (k) (x) = 22 . f (k) (log⋆ x) times. Therefore, g (k) (0) ≤ n implies f (k) (0) ≤ log⋆ n, which holds whenever k ∈ O(Tf (log⋆ n)), and the largest k satisfying this inequality is in Θ(Tf (log⋆ n)). For hypothesis, f (x) ≥ 2x. So log⋆ (g(x)) = f (log⋆ x) ≥ 2 log⋆ x ≥ log⋆ (2x), for any x ≥ 2. Hence, considering Remark 6, g(x) ≥ 2x for any x. Then, from Observation 8, it follows that the round complexity of the Increasing Degree problem Πg is Θ(Tf (log⋆ (n)). ◀ The proof of Theorem 13 defines an automatic translator Φ which transforms any function f satisfying f (x) ≥ 2x to a new function Φ(f ) satisfying  2 .. Φ(f )(x) = 22 . f (log⋆ x) times which in turn correspond to a Increasing Degree problem ΠΦ(f ) with complexity TΦ(f ) (n) = Θ(Tf (log⋆ n)). Section 3 describes infinitely many versions of the Increasing Degree problem, with complexities in the Chang-Pettie interval. Theorem 13 allows us to derive infinitely many new versions of the Increasing Degree problem, with different asymptotic complexities in [Ω(log⋆ log⋆ n), O(log⋆ n)]. The operator can even be iterated. Indeed, the function Φ(f ) resulting from the application of the operator grows much faster than f , and thus it is possible to apply Φ on Φ(f ) to obtain a Increasing Degree problem ΠΦ◦Φ(f ) with complexity TΦ◦Φ(f ) (n) ∈ [Ω(log⋆ log⋆ log⋆ n), O(log⋆ log⋆ n)]. In general, by iterating this process as many times as desired, we can obtain infinitely many different asymptotic complexity in the interval (k+1) (k) (k) [Ω(log⋆ n), O(log⋆ n)], for every k ∈ N, where log⋆ n is the function log⋆ applied k successive times starting from n, i.e., log⋆ (. . . (log⋆ (n)) . . . ) with k applications of log⋆ . Formally, combining Theorem 9 and Theorem 13, yields the following. ▶ Corollary 14. There exist locally checkable problems with the following round complexities

in n-node graphs: Θ (log⋆ log⋆ n), Θ logϵ (log⋆ n) for every ϵ ∈ (0, 1), and Θ log(k) (log⋆ n) for every integer k ≥ 1. More generally, ▶ Corollary 15. There exist locally checkable problems with the following round complexities

(r) (r) in n-node graphs, for every integer r ≥ 1: Θ log⋆ n , Θ logϵ (log⋆ n) for every ϵ ∈ (0, 1),
(r) and Θ log(k) (log⋆ n) for every integer k ≥ 1. We conclude this section by exhibiting a locally checkable problem with extremely small complexity, still in ω(1). ▶ Definition 16. The doubly iterated logarithm, or log-sharp, is the function that, evaluated on a natural number n, returns the number of times the iterated logarithm function, i.e. the function log⋆ , must be iteratively applied starting from n until the result is at most 1. Formally, the function log ♯ : N → N is defined as ( 0 if n ≤ 1; ♯ log (n) := ♯ ⋆ 1 + log (log n) if n > 1

15

16

A Simple Construction of Locally Checkable Problems Filling the Complexity Gaps

▶ Theorem 17. There exists a locally checkable problem with round complexity Tf (n) = Θ(log♯ n). Proof. Let f : N → N defined as ( 2 if x = 0, f (x) = f (x−1) 2 if x ≥ 1. Or, more informally, the function f is defined as  2 .. f (x) = 22 . x times Looking at this latter form, we immediately see that log⋆ (f (x)) = x. Composing f with itself we obtain:  2 . (2) .. f (x) = 22 f (x) times and we have log⋆ log⋆ (f (2) (x)) = x. More generally, for any integers k and x ≥ 1, it holds that log⋆(k) (f (k) (x)) = x and log⋆(k) (f (k) (0)) = 2. As usual
now, thanks to Observation 8, we look for the largest integer k satisfying n = Θ f (k) (0) . Applying k times the iterated logarithm to the previous equation we obtain log⋆(k) (n) = log⋆(k) (f (k) (0)) = 2. Therefore, k = Θ(log♯ n), as claimed.

5

◀

Filling up Polylogarithmic Complexity Gaps

In this section, we study round complexities that fill up the known gaps for LCL problems on bounded-degree trees in the polynomial and polylog regimes. The result for the polynomial regime had actually already been established in [24]. We provide a new construction, whose interest is that it can be leveraged for deriving new complexities in the polylog⋆ regime in graphs (cf. Corollary 22). ▶ Theorem 18. The following statement holds. 1. For every real s > 2, there exists a function fs : N → N such that the round complexity of the Increasing Degree problem Πfs is Θ(n1/s ). 2. For every real γ > 1, there exists a function fγ : N → N such that the round complexity of the Increasing Degree problem Πfγ is Θ(logγ n). In contrast to the previous sections, it is not direct to specify a function f whose associated problem Πf attains a desired round complexity. Instead, we adopt an inverse approach: √ given a target complexity T (n) ∈ [ω(log n), o( n)], we construct a function f such that Tf (n) ∈ Θ(T (n)). We formalize this approach in the following technical lemma. ▶ Lemma 19. Suppose that there exists an increasing sequence (αj )j≥1 ⊆ R>0 satisfying the following conditions.

F. Casagrande, P. Fraigniaud, B. Jauregui, M. Rabie

17

αj ≥ 5 for every j ≥ 1, αj+1 − αj ≥ αj − αj−1 for all j ≥ 2, and there exists a function T : N → N such that, for every n ∈ N, the largest integer k Pk−1 satisfying j=0 (k − j)αj ≤ n satisfies k ∈ Θ (T (n)) Then there exists a function f : N → N such that the round complexity of the Increasing Degree problem Πf is Θ(T (n)). Proof. Let (αj )j≥1 be a sequence satisfying the conditions of the statement. Let us consider functions of the form f (x) = x + g(x). Our objective is to determe g such that Πf has round complexity Θ((T (n)). To apply Observation 7, we need the values of f (i) (0) for all i. Let (βi )i≥1 defined as β1 = 2 + gs (2), and βi = βi−1 + g(βi−1 ) for all i ≥ 2. Thanks to a rearrangement of the sum, it holds that (k + 1) +

k X

f (i) (0) ≤ n ⇐⇒ (k + 4) +

i=1

k−1 X

((k − 2) − j)βj ≤ n.

(4)

j=0

We set βj = αj to derive the function g defined as g(0) = g(1) = 0, g(2) = α1 − 2, and, for every j ≥ 2, g(αj ) = αj − αj−1 . We extend g to all n ∈ N by defining g(n) = g(αj ), for every j ≥ 1, and every n satisfying αj ≤ n < αj+1 . Now consider f (x) = x + g(x) for this function g. By the first two conditions satisfied by the sequence (αj )j∈N we have that f (x) > x for all x ∈ N, and f is increasing. Furthermore, the equivalence of Eq. (4) holds. By the last condition satisfied by the sequence (αi )i≥1 , we can infer that, for any integer n, the desired largest integer k is in Θ (T (n)). This is because, since αi ≥ 1 for all
i, we have that the Pk−1 Pk−1 expression (k + 4) + j=0 ((k − 2) − j)αj belongs to Θ j=0 (k − j)αj . By Observation 7, the round complexity of Πf is in Θ (T (n)), as claimed. ◀ We have all the ingredients to prove Theorem 18. Proof of Theorem 18. Let us first prove the first item of the statement. Let s ≥ 2. By Lemma 19, it suffices to exhibit an increasing sequence (αj )j≥1 satisfying the hypotheses of the lemma, with T (n) = Θ(n1/s ). Let α be the sequence defined as αj = (4 + j)s−2 for every integer j ≥ 1. Since s ≥ 2, we have αj ≥ 5 for all j, and αj+1 − αj ≥ αj − αj−1 for all j ≥ 2. Rb 1 Finally, since a xt dx = t+1 (bt+1 − at+1 ), we have k X (k − j)j s−2 ∈ Θ (k s ) . j=1

We get that, for every n, the
largest integer satisfying the third condition in the statement 1/s of Lemma 19 is in Θ n . By Lemma 19 we conclude that there exists a function fs such
that the round complexity of the Increasing Degree problem Πfs is Θ n1/s . We move on with proving the second item of the statement. Fix γ > 1 be a real. By Lemma 19, it is sufficient to exhibit an increasing sequence (αj )j≥1 satisfying with 1/γ T (n) = Θ((log n)γ ), Let us define αj = 2j for every j ≥ 1. Up to exchanging the first two initial values, we can assume w.l.o.g. that αj ≥ 5 for every j and αj+1 − αj ≥ αj − αj−1 for every j ≥ 2. This does not affect the asymptotic estimates below. For every k, let Sk =

k X

(k − j)2j

1/γ

.

j=1

  1/γ ▷ Claim 20. Sk ∈ Θ k 2−21/γ 2k .

18

A Simple Construction of Locally Checkable Problems Filling the Complexity Gaps

Proof. For the upper bound, write j = k − r. Since x 7→ x1/γ is concave, it follows from the mean value theorem that there exists a constant c > 0 such that, for every 0 ≤ r ≤ k, k 1/γ − (k − r)1/γ ≥ c

r k 1−1/γ

.

As a consequence, 2(k−r)

1/γ

≤ 2k

1/γ

 exp −c′

r



k 1−1/γ

for some constant c′ > 0, and thus Sk =

k−1 X

r 2(k−r)

1/γ

≤ 2k

1/γ

r=0

k−1 X

 r · exp −c′

r=0

r k 1−1/γ



≤ C 2k

1/γ

k 2−21/γ .

For the lower bound, let us restrict the sum to 1 ≤ r ≤ c0 k 1−1/γ , where c0 > 0 is a sufficiently small constant. For such r, we have (k − r)1/γ ≥ k 1/γ − C for some constant C > 0. Thus 1/γ 1/γ 2(k−r) ≥ c 2k , and consequently ⌊c0 k1−1/γ ⌋

Sk ≥

X

⌊c0 k1−1/γ ⌋

r2

(k−r)1/γ

≥ c2

k1/γ

r=1

X

r ≥ c ′ 2k

1/γ

k 2−21/γ .

r=1

◀

This completes the proof of the claim. 1/γ

Since the polynomial factor k 2−21/γ is negligible compared with 2k
, the largest integer k such that Sk ≤ n satisfies k 1/γ = Θ(log n), and thus k = Θ (logγ n) . By Lemma 19,
there exists a function fγ : N → N such that the round complexity of Πfγ is Θ logγ n , which completes the proof of Theorem 18. ◀ Analogously to Theorem 13, one can transfer the round complexities in the range [ω(log n), o(n)] (obtained in Theorem 18) to the range [ω(log log⋆ n), o(log⋆ n)]. However, Theorem 13 cannot be applied directly in our setting. Indeed, the translation mechanism described there is only valid for functions satisfying f (x) ≥ 2x, whereas the functions constructed in Theorem 18 satisfy f (x) < 2x. Therefore, now we describe a new translator that enables us to transfer our desired complexities. ▶ Theorem 21. Let F be the family of all increasing functions f : N → N such that f (x) ≥ x and f (x + 1) ≥ f (x) + 1. There exists an operator Φ2 : F → F with the following property: For every function f ∈ F whose associated Increasing Degree problem Πf has round complexity Tf (n) ∈ ω(log n), the round complexity of the Increasing Degree problem ΠΦ2 (f ) is Θ (Tf (log⋆ n)). Proof. Let f ∈ F, define for each i ∈ N the partial sums Ai = f (i) (0) and Si = Then define the sequence βi = 2 2 .

..

2

Pi

j=1 Aj .

 Si times

and the function g = Φ2 (f ) as g(βi ) = βi+1 , g(x) = βi+1 for all x ∈ [βi , βi+1 ), and g(x) = β1 for all x ∈ [0, β1 ). By definition it holds that g (i) (0) ∈ Θ(βi ). As f (x + 1) ≥ x + 1, Pk the sum i=1 g (i) (0) is dominated by the last term, and therefore if k is the largest integer

F. Casagrande, P. Fraigniaud, B. Jauregui, M. Rabie

for which this sum is at most n, we have g (k) (0) ∈ Θ(n). Then log⋆ (βk ) is in Θ(log⋆ n), and by definition of βk Sk =

k X

f (i) (0) ≤ log⋆ n.

i=1

Therefore, by Observation 7 we conclude that k ∈ Θ(Tf (log⋆ n)), from which we conclude that the round complexity of the Increasing Degree problem Πg is Θ (Tf (log⋆ n)). ◀ By a direct application of Theorem 18 and Theorem 21, we obtain the following. ▶ Corollary 22. The following statement holds. 1. For every real s > 2, there exists a function fs : N →
N such that the round complexity of the Increasing Degree problem Πfs is Θ (log⋆ n)1/s . 2. For every real γ > 1, there exists a function fγ : N → N such that the round complexity of the Increasing Degree problem Πfγ is Θ(logγ log⋆ n).

6

√ Refined Complexities Above Ω( n)

In this section we present a variant of the Increasing Degree problem to obtain new complexities for locally checkable problems, of the form Θ(nα logβ n), for α ∈ [ 12 , 1) and β ≥ 1. This provides a refinement of the complexities of the form Θ(nα ) already observed in [24]. The intuition of our construction is the following. To obtain a small complexity Tf (n) for an Increasing Degree problem Πf , the associated function f has to grow fast. Conversely, √ Theorem 5 show that to obtain a Increasing Degree problem with complexity Θ( n), we used a slowing growing function, namely f (x) = x + 1. We therefore face a problem for √ obtaining a complexity Tf (n) = ω( n) as the associated function f : N → N has to satisfy f (x) > x, hence f (x) = x + 1 is the minimum that can be achieved under this constraint. √ In order to design a problem with complexity ω( n), one would like to use a function f satisfying f (x) = x+o(1), but no Increasing Degree problem Πf correspond to such a function. To resolve this issue, we borrow an idea from [24], which enables to use a particular structure that implicitly translate into using a slowly growing function f (x) = x + o(1). Roughly, we do not count the number of adjacent leaves, but the presence of specific structures in the vicinity. These structures are essentially trees that are associated to the representation of a partition of an integer. For the sake of completeness, let us recall some basic elements needed to define the aforementioned structured, following the ideas developed in [24]. ▶ Definition 23. A partition of a natural number n is an ordered sequence of non-necessarily Pk distinct integers L = (a1 , a2 , . . . , ak ), where 0 < a1 ≤ a2 ≤ · · · ≤ ak , satisfying i=1 ai = n. We denote by p(n) the number of distinct partitions of n. These partitions can be lexicographically ordered, and, for i ∈ {1, ..., p(n)}, we denote by Ln,i the i-th partition of n. For instance, we have p(3) = 3, and L3,1 = {1, 1, 1}, L3,2 = {1, 2}, L3,3 = {3}.  p  ▶ Lemma 24 ([19]). p(n) ∼ 4n1√3 exp π 2n/3 . We now formalize the tree structure from [24] that we use in our lower bound construction.

19

20

A Simple Construction of Locally Checkable Problems Filling the Complexity Gaps

T3,1

T3,2

T3,3

Figure 4 The three trees of depth at most 2 that correspond to the three partitions (1, 1, 1), (1, 2), and (3) of n = 3.

▶ Definition 25. Let Ln,i = {a1 , a2 , . . . , ak } be the ith partition of n ≥ 1. The partition tree Tn,i associated to this partition is a rooted tree, whose root v is referred to as the head of the tree. The head v has a child uj for every j ∈ {1, . . . , k}, and the node uj has aj − 1 ≥ 0 children, which are leaves of Tn,i . For instance, the p(3) = 3 partitions yields the three trees in Figure 4. Note that every node v can decide in two rounds whether it is the head of a partition tree Tn,i . We now define an ordering of partition trees, which express how we expect to find a “chain of partition trees” in the graph. ▶ Definition 26. Let α ∈ [ 12 , 1) and β ≥ 1 be reals. Let s := 2α−1 1−α , and q := β(s + 2). A node v is (α, β)-ordered if the following three conditions hold: 1. v is the head of a partition tree Tx,i for some positive integers i and x; 2. if i < ⌊xs logq x⌋ then v has a neighbor w that is the head of the partition tree Tx,i+1 ; 3. if i = ⌊xs logq x⌋ then v has a neighbor w that is the head of the partition tree T(x+1),1 . The node w appearing in the second and third conditions above is called the successor of v. For every α ∈ [1/2, 1) and β ≥ 1, we can now define a new problem Πα,β that extends the notion of Increasing Degree problem. We call Partition problem such a problem Πα,β . Partition problem Πα,β = (L, φα,β ) Labeling at node v: ℓ(v) = (ℓin (v), ℓout (v)) ∈ L = {0, 1} × {0, 1} = Lin × Lout Correctness predicate φα,β at node v:   φα,β = (v not ordered) ∧ (ℓout (v) = ℓin (v)) ∨ 
 (v ordered) ∧ ∃w ∈ N (v) : (w successor of v) ∧ (ℓout (v) = ℓout (w)) For each Partition problem Πα,β , the ordering condition, and the successor nodes are defined with respect to the parameters α and β of the problem. Similar to an Increasing Degree problem, a Partition problem asks every node to merely return its input, except for the nodes which are ordered, which must output the same output as their successors. Any problem Πα,β is locally checkable. Indeed, given a possible solution, any node can check in two rounds whether it is the head of a partition tree, and if so whether there it has a

F. Casagrande, P. Fraigniaud, B. Jauregui, M. Rabie

successor. The round complexity (in unbounded degree graphs) of a Partition problem is the following. ▶ Theorem 27. For every α ∈ [ 12 , 1) and β ≥ 1, the Partition problem Πα,β has round complexity Θ(nα logβ n) in n-node graphs. The lower bound Ω(nα logβ n) also holds for trees. Proof. Given α and β as hypothesis, let s = 2α−1 1−α and q = β(s + 2) as in Definition 26. For every positive integer k, let us consider a path P = (P1 , P2 , . . . , Pk ) composed of a series of sub-paths P1 , . . . , Pk where Pi = (vi,1 , . . . , vi,⌊is logq i⌋ ). In other words, the path P is subdivided in k “blocks” P1 , . . . , Pk , where the i-th block has length ⌊is logq i⌋. To prove the desired lower bound, we construct a tree T by attaching partition trees to each of the nodes of P . For every i ∈ {1, . . . , k}, and every j ∈ {1, . . . , ⌊is logq i⌋} we attach the tree Ti,j to vi,j , which becomes the head of Ti,j . For every i ∈ N, and every s, q ∈ R, the tree Ti,j exists for all j ≤ ⌊logq i⌋, as is logq (i) ≤ p(i) by Lemma 24. So the tree T is well defined. We call P the spine of T . Analogously to the proof of Theorem 2, the length d of the spine is a lower bound for the problem Πα,β . We have d := |P | =

k X

is logq i.

i=1

Since the function f (t) = ts logq (t) is monotonically increasing in the interval [1, ∞), for the integral test for convergence we have Z k Z k k X f (t) dt ≤ is logq i ≤ f (t) dt + f (k), 1

i=1

1

from which it follows that Z k d= ts logq (t) dt + O(k s logq k) = Θ(k s+1 logq k). 1

Pk On the other hand, the number of nodes of T is n = i=1 is+1 logq i. As a consequence, Z k n= ts+1 logq (t) dt + O(k s+1 logq k) = Θ(k s+2 logq k), 1

1 from which it follows that k = Θ lognq n s+2 . Plugging this latter value in the value of d, we get " !# s+1 s+1   q s+1 n s+2 n s+2 q s+2 s+2 d=Θ · log = Θ Cs,q · n · log n q q (log n) s+2 (log n) s+2 Where Cs,q is a value that depends only on s and q. Using the values of α and β, and the fact that both are fixed constants, we eventually get  αβ    d=Θ · nα · logβ n = Θ nα logβ n . 1−α The upper bound holds because of the construction of the tree T as a n-node graph. Indeed it includes P , the longest possible path of ordered nodes in a graph with n nodes. Then using an analogue version of ?? modified for Πα,β on any graph G, the round complexity cannot exceed the one needed for the hard instance T . ◀

21

22

A Simple Construction of Locally Checkable Problems Filling the Complexity Gaps

7

Conclusion

In this paper, we have shown that the gaps in the complexity landscape of LCL problems in the LOCAL model can be filled up with infinitely many different asymptotic complexities of explicit problems whenever the constraint on the maximum degree of the input graphs is discarded. The next step for a better understanding of the complexity landscape of locally checkable problems in the LOCAL model is to prove or disprove the existence of a mechanical way of solving Equation (2) in f for every given (computable) round complexity t(n), that is, to explicitly construct f such that the largest integer k satisfying f (k) (0) ≤ n is k = t(n). As a concrete example, what is an explicit expression of a function f such that the associated Increasing Degree problem Πf has round complexity equal to the inverse Ackermann function? Recall that the inverse Ackermann function is defined as follows. Let α1 (n) = ⌈n/2⌉, and, for every k ≥ 2, let αk (n) be the number of times we have to apply the function αk−1 starting from n until we reach a value at most 1, i.e., αk (1) = 0, and, αk (n) = 1+αk (αk−1 (n)) for n ≥ 2. In particular, α2 (n) = ⌈log2 n⌉, α3 (n) = log⋆ n, and α4 (n) = log♯ n. The inverse Ackermann function α(n) assigns to each integer n the smallest k for which αk (n) ≤ 3. To get a complexity α2 (n), we merely used Πf2 with f2 (x) = 2x, whereas, to get a complexity α3 (n), we used Πf3 with f3 (x) = 2x , and, to get a complexity α4 (n), we used Πf4 with  2 .. f4 (x) = 22 . x times. −1 More generally, for every index k ≥ 2, using Πfk with fk (n) = αk−1 (n) enables to define a locally checkable problem with complexity αk (n) in the LOCAL model. But what is the explicit expression of a function fack : N → N such that the associated Increasing Degree problem Πfack has complexity α(n) in the LOCAL model? The same question could be asked for the inverses of other rapidly growing functions such as the Friedman’s TREE function. And of course, the general question remains whether all round complexities can be obtained in arbitrary graphs, as it was shown [9] to be the case in the restricted case of trees?

References 1

2 3

4

5

6

Amirreza Akbari, Xavier Coiteux-Roy, Francesco d’Amore, François Le Gall, Henrik Lievonen, Darya Melnyk, Augusto Modanese, Shreyas Pai, Marc-Olivier Renou, Václav Rozhoň, and Jukka Suomela. Online locality meets distributed quantum computing. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, page 1295–1306, New York, NY, USA, 2025. Association for Computing Machinery. Dana Angluin. Local and global properties in networks of processors. In Proceedings of the twelfth annual ACM symposium on Theory of computing, pages 82–93, 1980. Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela. The distributed complexity of locally checkable problems on paths is decidable. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 262–271, 2019. Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Timothé Picavet, and Gustav Schmid. The distributed complexity landscape on trees depends on the knowledge about the network size. arXiv preprint arXiv:2605.12787, 2026. Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studenỳ, Jukka Suomela, and Aleksandr Tereshchenko. Locally checkable problems in rooted trees. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, pages 263–272, 2021. Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela. Almost global problems in the local model. In 32nd International Symposium on Distributed Computing, 2018.

F. Casagrande, P. Fraigniaud, B. Jauregui, M. Rabie

7

8

9

10

11

12

13

14

15 16

17

18

19 20 21 22 23 24 25

Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, Augusto Modanese, Dennis Olivetti, Mikaël Rabie, Jukka Suomela, and Jara Uitto. Shared randomness helps with local distributed problems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), pages 16–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2025. Alkida Balliu, Juho Hirvonen, Janne H Korhonen, Tuomo Lempiäinen, Dennis Olivetti, and Jukka Suomela. New classes of distributed time complexity. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1307–1318, 2018. Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron. How local constraints influence network diameter and applications to LCL generalizations. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024), 2024. Nicolas Bousquet, Laurent Feuilloley, and Sébastien Zeitoun. Complexity landscape for local certification. In 39th International Symposium on Distributed Computing. Schloss Dagstuhl– Leibniz-Zentrum für Informatik, 2025. Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto. A lower bound for the distributed lovász local lemma. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 479–488, 2016. Sebastian Brandt, Juho Hirvonen, Janne H Korhonen, Tuomo Lempiäinen, Patric RJ Östergård, Christopher Purcell, Joel Rybicki, Jukka Suomela, and Przemysław Uznański. Lcl problems on grids. In Proceedings of the ACM Symposium on Principles of Distributed Computing, pages 101–110, 2017. Yi-Jun Chang. The complexity landscape of distributed locally checkable problems on trees. In 34th International Symposium on Distributed Computing (DISC 2020), pages 18–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020. Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An exponential separation between randomized and deterministic complexity in the local model. SIAM Journal on Computing, 48(1):122–143, 2019. Yi-Jun Chang and Seth Pettie. A time hierarchy theorem for the local model. SIAM Journal on Computing, 48(1):33–69, 2019. Pierre Fraigniaud, Mika Göös, Amos Korman, and Jukka Suomela. What can be decided locally without identifiers? In 32nd ACM Symposium on Principles of Distributed Computing (PODC), pages 157–165, 2013. Mohsen Ghaffari and Hsin-Hao Su. Distributed degree splitting, edge coloring, and orientations. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’17, page 2505–2523, USA, 2017. Society for Industrial and Applied Mathematics. Christoph Grunau, Václav Rozhoň, and Sebastian Brandt. The landscape of distributed complexities on trees and beyond. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, pages 37–47, 2022. G. H. Hardy and S. Ramanujan. Asymptotic formulaæ in combinatory analysis. Proceedings of the London Mathematical Society, s2-17(1):75–115, 1918. Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on computing, 21(1):193–201, 1992. Moni Naor and Larry Stockmeyer. What can be computed locally? In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 184–193, 1993. David Peleg. Distributed computing: a locality-sensitive approach. SIAM, 2000. Chiara Piombi. Generalizing LCL complexity gaps to unbounded degree via monadic secondorder properties. In 40th International Symposium on Distributed Computing (DISC), 2026. Gustav Schmid. LCLs beyond bounded degrees. arXiv preprint arXiv:2602.02340, 2026. Jukka Suomela. Landscape of locality (invited talk). In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020), pages 2–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020.

23

Related documents

• AutoGraphForge: Towards Automated Graph Theory Discovery#926397
• A Survey of Densest Subgraph Discovery on Large Graphs#820128
• Graph-based automata#986471
• Verified Linear Programming through Tolerance-Aware Precision Boosting#1070495
• Assyrian Merchants meet Nuclear Physicists: History of the Early Contributions from Social Sciences to Computer Science. The Case of Automatic Pattern Detection in Graphs (1950s-1970s)#761084