Online Locality Meets Distributed
Quantum Computing

**Amirreza Akbari** · Aalto University, Finland

**Xavier Coiteux-Roy** · School of Computation, Information and Technology, Technical University of Munich, Germany · Munich Center for Quantum Science and Technology, Germany

**Francesco d'Amore** · Aalto University, Finland · Bocconi University, Italy · BIDSA, Italy

**François Le Gall** · Nagoya University, Japan

**Henrik Lievonen** · Aalto University, Finland

**Darya Melnyk** · Technische Universität Berlin, Germany

**Augusto Modanese** · Aalto University, Finland

**Shreyas Pai** · Aalto University, Finland

**Marc-Olivier Renou** · Inria, Université Paris-Saclay, Palaiseau, France · CPHT, Ecole Polytechnique, Institut Polytechnique de Paris, Palaiseau, France

**Václav Rozhoň** · ETH Zurich, Switzerland

**Jukka Suomela** · Aalto University, Finland

**Abstract.** We connect three distinct lines of research that have recently explored extensions of the classical LOCAL model of distributed computing:

A. distributed quantum computing and non-signaling distributions [e.g. STOC 2024],

B. finitely-dependent processes [e.g. Forum Math. Pi 2016], and

C. locality in online graph algorithms and dynamic graph algorithms [e.g. ICALP 2023].

We prove new results on the capabilities and limitations of all of these models of computing, for *locally checkable labeling problems* (LCLs). We show that all these settings can be sandwiched between the classical LOCAL model and what we call the *randomized online-LOCAL model*. Our work implies limitations on the *quantum advantage* in the distributed setting, and we also exhibit a new *barrier* for proving tighter bounds. Our main technical results are these:

1. All LCL problems solvable with locality $O(\log^* n)$ in the classical deterministic LOCAL model admit a finitely-dependent distribution with locality $O(1)$. This answers an open question by Holroyd [2024], and also presents a new barrier for proving bounds on distributed quantum advantage using causality-based arguments.

2. In rooted trees, if we can solve an LCL problem with locality $o(\log \log \log n)$ in the randomized online-LOCAL model (or any of the weaker models, such as quantum-LOCAL), we can solve it with locality $O(\log^* n)$ in the classical deterministic LOCAL model. One of many implications is that in rooted trees, $O(\log^* n)$ locality in quantum-LOCAL is not stronger than $O(\log^* n)$ locality in classical LOCAL.
# 1 Introduction

In this work, we connect three distinct lines of research that have recently explored extensions of the classical LOCAL model of distributed computing:

A. Distributed quantum computing and non-signaling distributions [3, 27, 36].

B. Finitely-dependent processes [44, 45, 47].

C. Locality in online graph algorithms and dynamic graph algorithms [2, 22].

We prove new results on the capabilities and limitations of all of these models of computing, for locally checkable labeling problems (LCLs), with the help of a unifying model that we call randomized online-LOCAL. Our work implies limitations on the quantum advantage in the distributed setting, and we also exhibit a new barrier for proving tighter bounds.

## 1.1 Highlights

Our main technical results are these:

1. **All LCL problems** solvable with locality $O(\log^* n)$ in the classical deterministic LOCAL model admit a finitely-dependent distribution, i.e., a bounded-dependence distribution with constant locality:

classical LOCAL algorithm, locality $O(\log^* n)$

↓

bounded-dependence distribution, locality $O(1)$

↓

non-signaling distribution, locality $O(1)$

This answers an open question by Holroyd [44]. This also presents a new barrier for proving bounds on distributed quantum advantage: all current quantum-LOCAL lower bounds are, in essence, lower bounds for non-signaling distributions, and our result shows that fundamentally different techniques will be needed to solve some of the biggest open questions in this area (e.g., showing that there is no constant-round quantum-LOCAL algorithm for coloring cycles).

2. **In rooted trees**, if we can solve an LCL problem with locality $o(\log \log \log n)$ in the randomized online-LOCAL model (or any of the weaker models, such as quantum-LOCAL), we can solve it with locality $O(\log^* n)$ in the classical deterministic LOCAL model:

quantum-LOCAL algorithm, locality $o(\log \log \log n)$

↓

bounded-dependence distribution, locality $o(\log \log \log n)$

↓

randomized online-LOCAL algorithm, locality $o(\log \log \log n)$

↓

classical LOCAL algorithm, locality $O(\log^* n)$

One of many implications is that in rooted trees, $O(\log^* n)$ locality in quantum-LOCAL is not stronger than $O(\log^* n)$ locality in classical LOCAL, and also finitely-dependent distributions are not stronger than $O(\log^* n)$ locality in classical LOCAL.

We will now proceed to explain what all of these terms and models mean, and how they are connected with each others.
## 1.2 Roadmap

As our main goal is to unify and relate several distinct models studied in prior work, we will need to introduce a fair number of models of computing. We recommend that the reader keep the roadmap that we have in Fig. 10 (final page) at hand while reading the introduction, in order to maintain a clear view of things, as well as to consult this overview again when needed.

We start our adventure in Section 1.3 by introducing the classical models that we have at the very top of Fig. 10 and then relate these to the current landscape of LCLs in Section 1.4. Next, we gradually work our way through the quantum as well as bounded-dependence and non-signaling models in Section 1.5, after which we take our first break. At this point, we are familiar with the top half of Fig. 10, and we are ready to state our first main contributions related to symmetry breaking with finitely-dependent processes in Section 1.6.

In Section 1.7, we then turn to models that at first may seem completely unrelated. They deal with locality in sequential, dynamic, and online settings. As we will see in Section 1.8, however, we can connect all of these models into a single hierarchy, with seemingly orthogonal models sandwiched between deterministic LOCAL and randomized online-LOCAL, and we can prove various strong results that connect the complexity landscape between these two extremes.

## 1.3 Classical models

Let us first recall the definitions of the classical models of distributed graph algorithms [54, 61] that form the foundation for our work; we keep it brief here and postpone formal definitions to Section 4.

* **Deterministic LOCAL:** Our input graph $G = (V, E)$ represents a computer network; each node $v \in V$ is a computer and each edge $\{u, v\} \in E$ is a communication link between two computers. Each node is labeled with a unique identifier from $\{1, 2, \dots, \text{poly}(|V|)\}$. All nodes follow the same distributed algorithm. Initially a node is only aware of its own identifier and its own degree. Computation proceeds in synchronous rounds, and in each round a node can send and receive a message to and from each neighbor and update its state. Eventually each node must stop and announce its local output (its part of the solution, e.g. in graph coloring its own color). The *running time*, *round complexity*, or *locality* of the algorithm is the (worst-case) number of rounds $T(n)$ until the algorithm stops in any $n$-node graph.

* **Randomized LOCAL:** As above, but each node also has a private source of random bits.

We also define the following variants (see e.g. [50] for more on the impact of shared global information):

* **Deterministic LOCAL (shared):** Deterministic LOCAL with shared global information. The set of nodes and their unique identifiers is globally known, and hence we also know $n = |V|$.

* **Randomized LOCAL (shared):** Randomized LOCAL with shared global information and shared randomness. The set of nodes and their unique identifiers is globally known, and in addition to the private sources of random bits, there is also a shared source of random bits that all nodes can access.

We can interpret the shared versions of the models so that we get to *see* the set of nodes $V$ and their unique identifiers in advance, and we can also *initialize* the nodes as we want based on this information (and hence in the randomized model, we can also initialize all nodes with the same shared random string), but the set of edges $E$ is only revealed later. This interpretation will be useful especially with the quantum models.
## 1.4 Landscape of LCL problems

There has been more than three decades of work on understanding the capabilities and limitations of the classical deterministic and randomized LOCAL models, but for our purposes most interesting is the recent line of work that has studied distributed algorithms for locally checkable labeling problems, or LCLs. This is a family of problems first introduced by Naor and Stockmeyer [57]. LCL problems are graph problems that can be defined by specifying a finite set of valid neighborhoods. Many natural problems belong to this family: coloring graphs of maximum degree $\Delta$ with $\Delta + 1$ colors, computing a maximal independent set, finding a maximal matching, etc.

Since 2016, we have seen a large body of work dedicated to understanding the computational complexity of LCL problems in the deterministic and randomized LOCAL models [4–9, 11, 16, 17, 19, 20, 34, 37, 39, 40, 62], and nowadays there are even algorithms and computer tools available for exploring such questions [9, 23, 59]. As a result of this large international research effort, a landscape of the localities of LCL problems emerges [64]. We can classify LCL problems in discrete classes based on their locality, and we also understand how much randomness helps in comparison with deterministic algorithms. Our main goal in this work is to extend this understanding of LCL problems far beyond the classical models, and especially explore what can be computed very fast in models that are much stronger than deterministic or randomized LOCAL.

## 1.5 Quantum-LOCAL and finitely-dependent processes

We start our exploration of stronger models with distributed quantum computation. The key question is understanding the distributed quantum advantage: what can we solve faster if our nodes are quantum computers and our edges are quantum communication channels? There is a long line of prior work exploring this theme in different models of distributed computing [3, 18, 27, 33, 35, 36, 43, 48, 49, 51, 52, 55, 66–68], but for our purposes these are the models of interest:

* **Quantum-LOCAL:** This model of computing is similar to the deterministic LOCAL model above, but now with quantum computers and quantum communication links. More precisely, the quantum computers manipulate local states consisting of an unbounded number of qubits with arbitrary unitary transformations, the communication links are quantum communication channels (adjacent nodes can exchange any number of qubits), and the local output can be the result of any quantum measurement.

* **Quantum-LOCAL (shared):** Quantum-LOCAL with shared global information and a shared quantum state. As above, but now the algorithm may inspect and manipulate the set of nodes (before any edges are revealed). In particular, it may initialize the nodes with a globally shared entangled state.

As quantum theory intrinsically involves randomness, quantum-LOCAL is at least as strong as randomized LOCAL. There are some (artificial) problems that are known to be solvable much faster in quantum-LOCAL than deterministic or randomized LOCAL [52]; however, whether any LCL admits such a quantum advantage is a major open question in the field.

Directly analyzing quantum-LOCAL is beyond the scope of current techniques. In essence, the only known technique for proving limitations of quantum-LOCAL is sandwiching it between the classical randomized-LOCAL model and more powerful models than quantum-LOCAL that do not explicitly refer to quantum information. These more powerful models are based on the physical causality principle (a.k.a. non-signaling principle). The idea is perhaps easiest to understand with the help of the following thought experiment:
**Example 1.1.** Fix a distributed algorithm $\mathcal{A}$ in the quantum-LOCAL model (with shared global information and quantum state) that runs in $T$ rounds on graphs with $n$ nodes. Let $G = (V, E)$ be some $n$-node input graph. Apply $\mathcal{A}$ repeatedly to $G$ to obtain some probability distribution $Y(G)$ of outputs. Now fix some subset of nodes $U \subseteq V$, and consider the restriction of $Y(G)$ to $U$, in notation $Y(G)|_U$. Let $G[U, T]$ be the radius-$T$ neighborhood of set $U$ in $G$. Now modify $G$ outside $G[U, T]$ to obtain a different $n$-node graph $G'$ with $G[U, T] = G'[U, T]$. Apply $\mathcal{A}$ to $G'$ repeatedly, and we obtain another probability distribution $Y(G')$ of outputs. If $Y(G)|_U \neq Y(G')|_U$, it would be possible to use $\mathcal{A}$ to transmit information in $T$ time steps between two parties, Alice and Bob, that are within distance $T+1$ from each other: Bob holds all nodes of $U$, and he can, therefore, observe $Y(G)|_U$, while Alice controls the graph outside $G[U, T] = G'[U, T]$, and she can, therefore, instantiate either $G$ or $G'$. This would enable Alice to send a signal to Bob even if no physical communication occurred from Alice to Bob (as they are at distance $T+1$ from each other and only $T$ communication steps occurred), and thus violate the non-signaling principle.

This thought experiment suggests the following definition, also known as the $\varphi$-LOCAL model and the causal model [3, 36]:

* **Non-signaling model:** We can produce an arbitrary output distribution as long as it does not violate the non-signaling principle: for any set of nodes $U$, modifying the structure of the input graph at more than a distance $T(n)$ from $U$ does not affect the output distribution of $U$.

We also need to introduce the following definition to better connect our work with the study of finitely-dependent processes and in particular finitely-dependent colorings [44, 45, 47]:

* **Bounded-dependence model:** We can produce an arbitrary output distribution as long as it does not violate the non-signaling principle, and, furthermore, distant parts are independent: if we fix any sets of nodes $U_1$ and $U_2$ such that their radius-$T(n)$ neighborhoods are disjoint, then the output labels of $U_1$ are independent of the output labels of $U_2$.

Now if we set $T(n) = O(1)$, algorithms in the bounded-dependence model are in essence what is usually called *finitely-dependent processes*.

Now we can connect all the above models with each others as follows, sandwiching the two versions of quantum-LOCAL between other models (see Appendix A for details; the connection with the non-signaling model is known [3, 36] but the connection with the bounded-dependence model is to our knowledge new):

<figure><img src="image_1.png" /></figure>

Here an arrow $M_1 \to M_2$ indicates that an algorithm with locality (or round complexity) $T(n)$ in model $M_1$ implies an algorithm with the same locality in $M_2$. For some problems it is possible to prove near-tight bounds for quantum-LOCAL by using diagram (1). For example, a very recent work [27] used these connections to prove limits for the distributed quantum advantage in approximate graph coloring: they prove an upper bound for the deterministic LOCAL model and a near-matching lower bound for the non-signaling model.
## 1.6 Contribution 1: symmetry breaking with finitely-dependent processes

Now we are ready to state our first contribution. Recall the following gap result by Chang et al. [21]: all LCL problems that can be solved with locality $O(\log n)$ in deterministic LOCAL or with locality $O(\log \log n)$ in randomized LOCAL can also be solved with locality $O(\log^* n)$ in deterministic LOCAL. The class of problems with locality $\Theta(\log^* n)$ contains in essence all symmetry-breaking problems: these are problems that could be solved with constant locality if only we had some means of breaking symmetry (e.g. distance-$k$ coloring for some constant $k$ would suffice). In Section 6 we show the following result:

**Theorem 1.2.** Let $\Pi$ be any LCL problem with locality $O(\log^* n)$ in the deterministic LOCAL model. Then $\Pi$ can be also solved with locality $O(1)$ in the bounded-dependence model. Furthermore, the resulting finitely-dependent processes are invariant under subgraph isomorphism.

Put otherwise, there is a finitely-dependent distribution over valid solutions of $\Pi$. Here the invariance under subgraph isomorphisms implies that, for any two graphs $G, H$ that share some isomorphic subgraphs $G'$ and $H'$ such that their radius-$O(1)$ neighborhoods are still isomorphic, the finitely-dependent processes solving $\Pi$ restricted to $G'$ and $H'$ are equal.

For any constant $d$, the task of coloring $d$-regular trees with $d+1$ colors is a problem with locality $O(\log^* n)$ in the deterministic LOCAL model. Hence, we can **answer the open question** by Holroyd [44]:

**Corollary 1.3.** For each $d \ge 2$, there is a finitely-dependent coloring with $d+1$ colors in $d$-regular trees. Furthermore, the resulting process is invariant over subgraph isomorphisms.

More specifically, there exists a finitely-dependent 4-coloring distribution of the infinite 3-regular tree that is invariant under automorphisms.

Theorem 1.2 also introduces a formal **barrier** for proving limitations on distributed quantum advantage. Recall that all current quantum-LOCAL lower bounds are, in essence, lower bounds in the non-signaling model. Before our work, there was a hope that we could discover a symmetry-breaking problem $\Pi$ with the following properties: (1) its locality is $O(\log^* n)$ in deterministic LOCAL, and (2) we can show that its locality is $\Omega(\log^* n)$ in the non-signaling model, and therefore (3) $\Pi$ cannot admit any distributed quantum advantage. However, our work shows that no such problem $\Pi$ can exist. In particular, arguments related to non-signal distributions are not sufficient to exclude distributed quantum advantage in this region.

## 1.7 Locality in online and dynamic settings

Let us now switch gears and consider a very different line of work. Ghaffari et al. [38] introduced a sequential counterpart of the classical LOCAL model:

* **Deterministic SLOCAL model:** The nodes are processed in an adversarial order. When a node $v$ is processed, the algorithm gets to see all information in its radius-$T(n)$ neighborhood (including states and outputs of previously processed nodes). The algorithm has to label $v$ with its local output, and the algorithm can also record other information in $v$, which it can exploit when other nodes near $v$ are later processed.

* **Randomized SLOCAL model:** As above, with access to a source of random bits.

Clearly SLOCAL is stronger than LOCAL. One key feature is that the processing order naturally breaks symmetry, and all symmetry-breaking LCLs can be solved with $O(1)$ locality in SLOCAL.
One interpretation of our first contribution is that we also establish a new, unexpected similarity between SLOCAL and the bounded-dependence model: both are able to solve any symmetry-breaking LCL with constant locality.

A recent work [2] introduced the following models that capture the notion of locality also in the context of centralized dynamic graph algorithms and centralized online graph algorithms:

* **Deterministic dynamic-LOCAL model:** The adversary constructs the graph one edge at a time. The algorithm has a global view of the graph (including states and outputs of previously processed nodes), but it has to maintain a feasible solution after each update. The algorithm is restricted so that after a modification at node $v$, it can only update the solution within distance $T(n)$ from $v$.

* **Deterministic online-LOCAL model:** The adversary presents the input graph one node at a time. When a node $v$ is presented, the adversary also reveals the radius-$T(n)$ neighborhood of $v$. The algorithm has to then choose the output label of $v$. Crucially, the algorithm has access to a global view of the graph (including states and outputs of previously processed nodes). This model can be seen as a stronger version of the deterministic SLOCAL model where all nodes have access to some global shared memory.

Both SLOCAL and dynamic-LOCAL can be sandwiched between LOCAL and online-LOCAL [2]:

$$ \begin{array}{ccc} \text{deterministic } \mathbf{LOCAL} & \longrightarrow & \text{deterministic } \mathbf{SLOCAL} \\ \downarrow & & \downarrow \\ \text{deterministic dynamic-LOCAL} & \longrightarrow & \text{deterministic online-LOCAL} \end{array} \qquad (2) $$

There are also some problems in which deterministic online-LOCAL is much stronger than deterministic LOCAL: 3-coloring in bipartite graphs has locality $\tilde{O}(\sqrt{n})$ in deterministic LOCAL [17, 27] but $O(\log n)$ in online-LOCAL [2]; very recently Chang et al. [22] also showed that this is tight for online-LOCAL.

## 1.8 Contribution 2: connecting all models for LCLs in rooted trees

At first sight, the models discussed in Sections 1.5 and 1.7 seem to have very little in common; they seem to be orthogonal extensions of the classical deterministic LOCAL model. Furthermore, we have already seen evidence that online-LOCAL can be much stronger than deterministic LOCAL. Nevertheless, we can connect all these models in a unified manner, and prove strong limits on their expressive power. To this end, we introduce yet another model:

* **Randomized online-LOCAL model:** Like deterministic online-LOCAL, but the algorithm has access to a source of random bits, and we play against an oblivious adversary (the adversary fixes the graph and the order of presenting nodes before the algorithm starts to flip coins).

Trivially, this is at least as strong as all models in diagram (2). However, the big surprise is that it is also at least as strong as all models in diagram (1). In Section 5 we prove:

**Theorem 1.4.** Any LCL that can be solved in the non-signaling model with locality $T(n)$ can also be solved in the randomized online-LOCAL model with the same locality.

Then we zoom into the case of rooted trees in Section 7 and prove:

**Theorem 1.5.** Any LCL on rooted trees that can be solved in the randomized online-LOCAL model with locality $o(\log \log \log n)$ can also be solved in the deterministic LOCAL model with locality $O(\log^* n)$.
Together with Theorem 1.2 and previously-known results, we also obtain the following corollary:

**Corollary 1.6.** In rooted trees, the following families of LCLs are the same:

* locality $O(\log^* n)$ in deterministic or randomized LOCAL or quantum-LOCAL,

* locality $O(1)$ in bounded-dependence model, non-signaling model, deterministic or randomized SLOCAL, dynamic-LOCAL, or deterministic or randomized online-LOCAL.

In rooted trees, there is no LCL problem with locality between $\omega(\log^* n)$ and $o(\log \log \log n)$ in any of these models: deterministic and randomized LOCAL, quantum-LOCAL, bounded-dependence model, non-signaling model, deterministic and randomized SLOCAL, dynamic-LOCAL, and deterministic and randomized online-LOCAL.

In particular, when we look at LCLs in rooted trees, $O(\log^* n)$-round quantum algorithms are not any stronger than $O(\log^* n)$-round classical algorithms. (However, it is still possible that there are some LCLs in trees that can be solved in $O(1)$ rounds in quantum-LOCAL and that require $\Theta(\log^* n)$ rounds in deterministic LOCAL; recall the discussion in Section 1.6.)

Theorem 1.5 can be seen as an extension of the result of Akbari et al. [2] that connects deterministic online-LOCAL with LOCAL for LCLs on rooted regular trees without inputs. Our result is applicable to the randomized online-LOCAL (and hence we can connect it with the non-signaling and quantum models), and it holds for any LCLs on rooted trees (possibly with irregularities and inputs). Recall that the presence of inputs makes a huge difference already in the case of directed paths [5, 23], and we need fundamentally new ideas, as we can no longer build on the classification from [9, 11].

## 1.9 Big picture

By putting together all our contributions (including some auxiliary results that we discuss later in Section 3), the landscape shown in Fig. 10 emerges. We can sandwich all models between deterministic LOCAL and randomized online-LOCAL. Going downwards, we get symmetry breaking for free (as indicated by the blue arrows). And in the case of rooted trees, for the low-locality region $o(\log \log \log n)$, we can also navigate upwards (as indicated by the orange arrows). Table 1 gives some concrete examples of localities for LCL problems across the landscape of models.

<table><caption>Table 1: Examples of localities across the models. Here symmetry-breaking problems refer to LCL problems with locality $\Theta(\log^* n)$ in the deterministic LOCAL model; this includes many classical problems such as maximal independent set, maximal matching, and $(\Delta + 1)$-vertex coloring.</caption><thead><tr><th>Model</th><th>Symmetry-breaking problems</th><th>3-coloring in bipartite graphs</th></tr></thead><tbody><tr><td>Deterministic LOCAL</td><td>Θ( log<sup>*</sup> n ) by definition</td><td>Θ̃( √n ) [27]</td></tr><tr><td>Randomized LOCAL</td><td>Θ( log<sup>*</sup> n ) [19]</td><td>Θ̃( √n ) [27]</td></tr><tr><td>Quantum LOCAL</td><td>O( log<sup>*</sup> n ) trivial</td><td>Θ̃( √n ) [27]</td></tr><tr><td>Bounded-dependence</td><td>O(1)</td><td>Θ̃( √n ) [27]</td></tr><tr><td>Deterministic SLOCAL</td><td>O(1)</td><td>Õ( √n ), n<sup>Ω(1)</sup> [2, 27]</td></tr><tr><td>Randomized SLOCAL</td><td>O(1)</td><td>Õ( √n ), n<sup>Ω(1)</sup> [2, 27]</td></tr><tr><td>Deterministic dynamic-LOCAL</td><td>O(1)</td><td>Õ( √n ), Ω( log n ) [22, 27]</td></tr><tr><td>Deterministic online-LOCAL</td><td>O(1)</td><td>Θ( log n ) [2, 22]</td></tr><tr><td>Randomized online-LOCAL</td><td>O(1)</td><td>Θ( log n ) Theorem 8.1</td></tr></tbody></table>
## 2 Overview of techniques and key ideas

In this section, we give an overview of the techniques and key ideas that we use to prove our main results, and we also provide a roadmap to the rest of this paper. We note that our first contribution is presented in Section 6, while the second contribution comes before it in Section 5—the proofs are ordered this way since Section 5 also develops definitions that will be useful in Section 6.

### 2.1 Bounded-dependence model can break symmetry (Section 6)

Let us first present an overview of the proof of Theorem 1.2 from Section 1.6. We show that the bounded-dependence model can break symmetry with constant locality; that is, there is a finitely-dependent process for any symmetry-breaking LCL.

It is well known that any LCL problem $Π$ that has complexity $O(\log^* n)$ in the **LOCAL** model has the following property: there exists a constant $k \in \mathbb{N}_+$ (that depends only on the hidden constant in $O(\log^* n)$) such that, if the graph is given a distance-$k$ coloring (with sufficiently small number of colors) as an input, then $Π$ is solvable in time $O(1)$ in the **LOCAL** model (using the distance-$k$ coloring as a local assignment of identifiers) [20].

We prove that for each bounded-degree graph, there is a finitely-dependent process providing a distance-$k$ coloring for constant $k$. Then, we can combine such a process with the **LOCAL** algorithm that solves the problem with locality $O(1)$ if a distance-$k$ coloring is given, and we prove that the resulting process is still a finitely-dependent distribution. Furthermore, we also prove that all these processes are invariant under subgraph isomorphisms (even those that do not preserve node identifiers), meaning that, for any two graphs $G$ and $H$ sharing two isomorphic subgraphs with isomorphic radius-$O(1)$ neighborhoods, the restrictions of the finitely-dependent processes solving $Π$ over $G$ and $H$ restricted to $G'$ and $H'$ are equal in law.

One of the key observations that we use is that **LOCAL** algorithms that do not exploit the specific assignment of node identifiers and do not depend on the size of the graph provide finitely-dependent distributions that are invariant under subgraph isomorphisms whenever the input labeling for the graphs is invariant under subgraph isomorphisms.

**Overview.** The cornerstone of our proof is a surprising result by Holroyd and Liggett [45] and its follow-up in [47], that state that there exist $k$-dependent distributions giving a $q$-coloring of the infinite path and of cycles for $(k, q) \in \{(1, 4), (2, 3)\}$ that are invariant under subgraph isomorphisms.

Recently, Holroyd has combined the finitely-dependent distributions of infinite paths to provide a finitely-dependent 4-coloring of the $d$-dimensional lattice [44]. Getting a translation invariant distribution is quite easy: First, use the distributions for the paths on each horizontal and vertical path obtaining a distance-$k$ coloring (with $k$ being a large enough constant) of the lattice with constantly many colors as shown in [45, Corollary 20]. Second, apply some **LOCAL** algorithm that starts from a distance-$k$ coloring and reduces the number of colors to 4 while keeping the resulting distribution symmetric (e.g., the algorithms from [10, 17]). The major contribution of [44] is transforming such a distribution into a process that is invariant under subgraph isomorphisms. However, this *symmetrization* phase is quite specific to the considered topology.

We come up with a new approach that obtains similar results in all bounded-degree graphs through the following steps:

1. We show that the finitely-dependent coloring of paths and cycles can be combined to obtain finitely-dependent 3-coloring distributions of rooted pseudoforests of bounded-degree that are invariant under subgraph isomorphisms.
2. We observe that all graphs of bounded-degree admit a random decomposition in rooted pseudoforests that satisfies the required symmetry properties.

3. We prove that such a random decomposition can be combined with the finitely-dependent 3-coloring of rooted pseudoforests to obtain finitely-dependent distributions that give a $(\Delta+1)$-coloring of graphs of maximum degree $\Delta$ that are invariant under subgraph isomorphism.

4. We show that we can use this finitely-dependent $(\Delta + 1)$-coloring distributions to provide a distance-$k$ coloring for bounded-degree graphs, which is enough to simulate any $O(\log^* n)$-round LOCAL algorithms that solves an LCL $\Pi$. Such combinations result in finitely-dependent processes that are invariant under subgraph-isomorphisms and solve $\Pi$.

Notice that, in spirit, steps 1 to 3 are similar to the steps needed to produce a $(\Delta + 1)$-coloring in time $O(\log^* n)$ in the LOCAL model [42, 60]: however, the detailed way these steps are obtained in the bounded-dependence model is quite different and requires a careful analysis.

**Step 1: Finitely-dependent 3-coloring distributions of rooted pseudoforests.** A rooted pseudoforest is a directed graph in which each node has outdegree at most 1. Let us now fix any rooted pseudoforest of maximum degree $\Delta$. Consider the following process: each node $v$ colors its in-neighbors with a uniformly randomly permutation of $\{1, \dots, \text{indeg}(v)\}$. The graph $G_i$ induced by nodes colored with color $i$ is a union of directed paths and cycles (see Fig. 1) and, hence, admits a finitely-dependent 4-coloring given by [45] that is invariant under subgraph isomorphisms; if a node is isolated, it can deterministically join any of the $G_i$s, say $G_1$. The sequence of graphs $(G_1, \dots, G_{\Delta_{\text{in}}})$ is said to be a random $\Delta_{\text{in}}$-decomposition of the rooted pseudoforest. Furthermore, if two graphs $G, H$ have isomorphic subgraphs $G', H'$ (together with some constant-radius neighborhoods), the decompositions in directed paths and cycles induced in $G'$ and $H'$ have the same distribution (because node colors are locally chosen uniformly). We prove that the combination of the random decomposition and the finitely-dependent coloring yields a finitely-dependent $4\Delta$-coloring which is invariant under subgraph isomorphisms: by further combining such distribution with the Cole-Vishkin color reduction algorithm [29, 42, 60] (that has complexity $O(\log^* k)$ with $k$ being the size of the input coloring), we can obtain a finitely-dependent 3-coloring distribution for rooted pseudoforests of maximum degree $\Delta$ that is invariant under subgraph isomorphisms.

**Steps 2-3: Finitely-dependent ($\Delta + 1$)-coloring distribution of bounded-degree graphs.** First, if the input graph is undirected, make it a directed graph by duplicating all edges and assigning both orientations to duplicated edges. Since a coloring of the nodes can be given in both cases equivalently, we focus on the directed case for simplicity. Second, consider the following process: each node $v$ labels its out-edges with a uniformly sampled permutation of the elements of $\{1, \dots, \text{outdeg}(v)\}$; this way we obtain a random decomposition of the edges of the graph into rooted pseudoforests, as each node has at most one out-edge with label $i$. Furthermore, if two graphs $G, H$ have isomorphic subgraphs $G', H'$ (together with some constant-radius neighborhoods), the decompositions induced in $G'$ and $H'$ have the same distribution (because edge labelings are locally chosen uniformly). We prove that if we apply the finitely-dependent 3-coloring from step 1 to each pseudoforest, we obtain a finitely-dependent $3^\Delta$-coloring of the input graph which is invariant under subgraph isomorphisms. By further combining such a distribution with a variant of the Cole-Vishkin color reduction algorithm, we obtain a finitely-dependent $(\Delta + 1)$-coloring distribution for bounded-degree graphs of maximum degree $\Delta$ that is invariant under subgraph isomorphisms.

**Step 4: Finitely-dependent distribution solving $\Pi$.** Consider any graph $G$ of maximum degree $\Delta$, and its $k$-th power graph defined as follows: simply add edges to $G$ between each pair of
nodes at distance at most $k$, where $k$ is some large enough constant. Observe that $G^k$ is a graph of maximum degree $\Delta^k$. Now, step 3 implies that there is a finitely-dependent ($\Delta^k + 1$)-coloring of $G^k$ that is invariant under subgraph isomorphisms: such distribution yields a distance-$k$ coloring of $G$. For any LCL $\Pi$ that has complexity $O(\log^* n)$ in LOCAL, we know that there exists a constant $k$ such that, if given a distance-$k$ coloring in input (with a constant number of colors), then there is an $O(1)$-round port-numbering algorithm solving $\Pi$ [20]: the combination of the input distance-$k$ coloring of $G$ given by step 2-3 with such an algorithm yields a finitely-dependent distribution solving $\Pi$ that is invariant under subgraph isomorphisms.

**Random decomposition of a graph.** In steps 1 and 3 we proceed in an analogous way: First, we construct a process that induces a random decomposition of a graph. Second, we consider finitely-dependent distributions of output labelings over the outputs of the random decomposition. The combination of the random decomposition and the finitely-dependent distributions gives rise to a process over the whole graph. In Section 6, we derive a general result (Lemma 6.8) which gives sufficient conditions on the random decomposition and the finitely-dependent distributions in order to ensure the final process is still finitely-dependent (possibly with symmetry properties). Lemma 6.8 is then the tool used in practice in steps 1 and 3.

**Independent related work.** Very recently, an independent and parallel work provided a finitely-dependent coloring of bounded-degree graphs with exponentially many colors (in the degree of the graph) [65]. The technique employed in [65] is very similar to ours: it exploits the decomposition of graphs in rooted pseudoforests, and then colors rooted pseudoforests using the finitely-dependent coloring of paths and cycles [45, 47]. However, [65] stops at the mere coloring problem and does not make use of color reduction algorithms, which are the key ingredient for extending results to all symmetry-breaking LCLs.

## 2.2 Simulating non-signaling in randomized online-LOCAL (Section 5)

Let us now give the intuition behind the proof of Theorem 1.4 from Section 1.8: we show that the non-signaling model can be simulated in randomized online-LOCAL without any loss in the locality.

A randomized online-LOCAL algorithm is given in input the size of the input graph, and a distribution that is non-signaling beyond distance $T$ and that solves some problem $\Pi$ over some graph family $\mathcal{F}$. When the adversary picks any node $v_1$ and shows to the randomized online-LOCAL algorithm its radius-$T$ neighborhood, the randomized online-LOCAL algorithm simply goes over all graphs of $n$ nodes in $\mathcal{F}$ until it finds one, say $H_1$, that includes the radius-$T$ neighborhood of $v_1$: then, it samples an output according to the restriction of the non-signaling distribution in $H_1$ to $v_1$. Notice that such distribution does not change if the topology of the graph changes outside the radius-$T$ neighborhood of $v_1$. Recursively, when the adversary picks the $i$-th node $v_i$, the randomized online-LOCAL algorithm goes over all graphs of $n$ nodes in $\mathcal{F}$ until it finds one, say $H_i$, that includes the union of radius-$T$ neighborhoods of $v_1, \dots, v_i$ (it must necessarily exist as the graph chosen by the adversary is a valid input): hence, it samples an output according to the restriction of the non-signaling distributions in $H_i$ to $v_i$ conditional on the outputs of $v_1, \dots, v_{i-1}$. We prove that the non-signaling property ensures that the algorithm described above fails with at most the same probability of failure of the non-signaling distribution.
## 2.3 Online-LOCAL can be simulated in SLOCAL for rooted trees (Section 7)

Next we give an overview of the proof of Theorem 1.5 from Section 1.8: we show that a randomized online-LOCAL algorithm that solves an LCL problem in rooted trees with locality $o(\log \log \log n)$ can be simulated in the deterministic SLOCAL model with locality $O(1)$, and therefore also in the deterministic LOCAL model with locality $O(\log^* n)$.

Online-LOCAL algorithms can be seen simply as SLOCAL algorithms with global memory. Notice that SLOCAL algorithms instead only have a form of “incremental” memory, i.e., they keep track of an incremental sequence of intersecting neighborhoods $N_1, N_2, \dots$, where $N_i$ intersects $N_{i+1}$.

The new ingredient we use in this section are component-wise online-LOCAL algorithms. Roughly speaking, a component-wise algorithm is a deterministic online-LOCAL algorithm that, when processing a node $v$, uses information only coming from the connected component of the input graph that has been revealed so far to which $v$ belongs, and nothing else. (If two or more components are merged, then the algorithm may use information it knows from any component.)

We prove Theorem 1.5 in three steps:

1. We first show that any randomized online-LOCAL algorithm solving an LCL with locality $T(n)$ can be turned into a deterministic component-wise online-LOCAL algorithm with locality $T(2^{O(2^{n^2})})$.

2. We then prove that, for LCLs on rooted trees, we can simulate the component-wise algorithms in SLOCAL.

3. Finally, we show that SLOCAL algorithms solving any LCL $\Pi$ with locality $o(\log n)$ over rooted trees can be turned into an $O(\log^* n)$-round LOCAL algorithm solving $\Pi$ over rooted trees.

**Step 1: Constructing component-wise algorithms from deterministic online-LOCAL algorithms.** To give some intuition, consider an LCL problem $\Pi$ on a family $\mathcal{F}$ of graphs that is closed under disjoint graph union and node and edge removals. Suppose there is a deterministic online-LOCAL algorithm $\mathcal{A}$ solving $\Pi$ with locality $T(n)$ on $n$-node graphs. Note that the output label $\mathcal{A}$ chooses for a node may depend arbitrarily on everything the algorithm has seen so far.

We show how to turn algorithm $\mathcal{A}$ into an algorithm whose output for isolated nodes depends only on the local topology and inputs and is oblivious to any previously-processed nodes. We call such algorithms 1-amnesiac. Here with isolated we mean the node $v$ is such that all nodes belong to the radius $T$-neighborhood around $v$ are new to algorithm $\mathcal{A}$, that is, $\mathcal{A}$ has no knowledge of how $v$ is connected (if at all) to the parts of the graph it has seen thus far.

Let $N_1 = |\Sigma_{\text{out}}| |\Sigma_{\text{in}}|^n \cdot 2^{n^2} \cdot n^2$, and let $\mathcal{G}_1$ be the set of all possible subgraphs of any $n$-node graphs (from $\mathcal{F}$) with inputs (up to isomorphisms) that are the radius-$T(N_1)$ neighborhood of some node, which we call the center of the neighborhood. Let $g_1 = |\mathcal{G}_1|$ and notice that $g_1 \le 2^{n^2} |\Sigma_{\text{in}}|^n$. Consider now the following experiment:

1. Construct a simulation graph $H_1$ that consists of $|\Sigma_{\text{out}}| \cdot n$ copies of all graphs in $\mathcal{G}_1$. The size of $H_1$ is at most $N_1 = n^2 |\Sigma_{\text{out}}| \cdot g_1 \le |\Sigma_{\text{out}}| |\Sigma_{\text{in}}|^n \cdot 2^{n^2} \cdot n^2$.

2. Reveal the center node of each of those neighborhood graphs to $\mathcal{A}$ in an arbitrary order with locality $T(N_1)$. For each type of radius-$T(N_1)$ neighborhood $\mathcal{T}_1$ (i.e., any element of $\mathcal{G}_1$), there exists some output label $\sigma_{\mathcal{T}_1}$ that occurs at least $n$ times. We call such neighborhoods good and such a label a canonical labeling of $\mathcal{T}_1$.

3. Continue labelling nodes of $H_1$ using $\mathcal{A}$ under an arbitrary ordering of the nodes.

We describe a new online-LOCAL algorithm $\mathcal{B}$ that, using this experiment, produces a correct labeling. Let $\mathcal{G}$ be an input graph $n$ nodes, and let node $v$ be revealed to $\mathcal{B}$ along with its radius-$T'(n)$ neighborhood, where $T'(n) = T(N_1)$. Whenever $v$ is an isolated node, algorithm $\mathcal{B}$ finds
a “fresh” (i.e., not previously chosen) good neighborhood in the experiment graph matching the radius-$T(N_1)$ neighborhood of $v$ in $G$. It then takes that unused good neighborhood, identifies all nodes with the revealed input neighborhood, and labels $v$ accordingly. An unused good neighborhood always exists since there are at least $n$ good neighborhoods in the experiment graph matching the radius-$T(N_1)$ neighborhood of $v$ in $G$. Algorithm $\mathcal{B}$ effectively cuts and pastes the neighborhood from the experiment graph to the actual input graph *without algorithm A noticing*. For non-isolated nodes, $\mathcal{B}$ just simulates what $\mathcal{A}$ would do, following the adversarial order of the nodes presented to $\mathcal{B}$. This is always possible because the labels of isolated nodes come from valid online-LOCAL runs of $\mathcal{A}$.

The correctness of algorithm $\mathcal{B}$ follows from that of $\mathcal{A}$. Moreover, when labeling an isolated node, $\mathcal{B}$ always labels it in the same way that depends only on the local structure and inputs of the graph; hence $\mathcal{B}$ is 1-amnesiac. Clearly, there is an exponential overhead in the locality: the locality of $\mathcal{B}$ is $T'(n) = T(N_1) = T(2^{O(n^2)})$.

Using the above, we now describe how to obtain a 2-amnesiac algorithm, that is, an algorithm that always produces the same labels for the same types of connected components formed by the union of intersecting neighborhoods of two distinct nodes. We modify the previous experiment as follows:

1. First we must increase the size of the experiment graph. Let $N_2 = |\Sigma_{\text{out}}|^2 |\Sigma_{\text{in}}|^n \cdot 2^n \cdot n^2$ and redefine $G_1$ with the radius-$T(N_2)$ neighborhoods.

2. Instead of considering $|\Sigma_{\text{out}}| \cdot n$ many disjoint copies of elements of $G_1$, we now take $|\Sigma_{\text{out}}|^2 \cdot n$ copies. By the same argument as before, there are at least $n \cdot |\Sigma_{\text{out}}|$ good neighborhoods.

3. Let $G_2$ be the set of all possible unions of two non-disjoint radius-$T(N_2)$ neighborhoods of two different nodes of any $n$-node graph (in $\mathcal{F}$), with all possible input labelings and orderings of the center nodes. Notice that the size of $G_2$ is $g_2 \le 2^{n^2} |\Sigma_{\text{in}}|^n$. We take $|\Sigma_{\text{out}}| \cdot n$ many disjoint copies of all graphs in $G_2$, with the catch that the neighborhood of the center node that comes first in the processing order is chosen arbitrarily among the good neighborhoods. The resulting graph $H_2$ is our new experiment graph, whose size is now $N_2 \le |\Sigma_{\text{out}}| |\Sigma_{\text{in}}|^n \cdot 2^{n^2} \cdot n^3$.

4. Use $\mathcal{A}$ to label all nodes that come first in the input order in each graph, then all nodes that come second in the same respective order.

5. Use $\mathcal{A}$ to label the second center node of each connected component. By the pigeonhole principle, for all types of such connected components $\mathcal{T}_2$ there are at least $n$ identical labelings. These make out the canonical labelings $\sigma_{\mathcal{T}_2}$.

The 2-amnesiac algorithm $\mathcal{B}$ starts by running the above experiment. When given in input an $n$-node graphs, it outputs the canonical labeling $\sigma_{\mathcal{T}_1}$ for isolated nodes whose radius-$T'(n) = T(N_2)$ neighborhood matches type $\mathcal{T}_1$. Similarly, $\mathcal{B}$ outputs the canonical labeling $\sigma_{\mathcal{T}_2}$ for nodes seeing a connected component of type $\mathcal{T}_2$ when we look at their radius-$T'(n) = T(N_2)$ neighborhood. The correctness argument is the same as that for 1-amnesiac algorithms. For the remaining nodes, $\mathcal{B}$ just simulates $\mathcal{A}$ using global memory as usual.

We can continue this process all the way up to $n$-amnesiac algorithms, which are simply component-wise online-LOCAL algorithms. See Lemma 7.5 for the formal details. As a remark, notice the restriction to LCLs is necessary to prove correctness: if the amnesiac algorithm fails, it must fail locally; hence also the original online-LOCAL algorithm fails locally, contradicting its correctness.

**Dealing with randomness.** Let us now turn to the setting where $\mathcal{A}$ is randomized. For deterministic online-LOCAL algorithms, we adaptively picked the good neighborhoods before processing further; however, since in randomized online-LOCAL the adversary is *oblivious*, we must adapt our strategy.
Our experiment graph $H_n$ is now *random*. It is constructed exactly as before, though now the good connected components have to be “guessed” uniformly at random each time. Clearly, the probability that our guesses are good is incredibly small. Hence we would like to amplify the success probability so that the probability that the guesses are good enough *and* the randomized online-LOCAL algorithm works correctly is bounded away from zero. (Once we have this, we may apply a standard derandomization argument.) The amplification is by replicating $k$ times the experiment graph $H_n$, guessing the good components for each copy of $H_n$ independently. Since the randomness of the algorithm and the randomness of these guesses are independent for each copy of $H_n$, a simple union bound together with the inclusion-exclusion principle give a positive probability that, in at least one copy of $H_n$, the guesses are correct and the algorithm works properly.

We now apply a standard derandomization argument: Since there exists an assignment of a random bit string to the randomized online-LOCAL algorithm as well as for “guessing” the good components in the $k$ copies of the experiment graph, there is a fixed, deterministic realization of $H_n$ that yields a (correct) deterministic online-LOCAL algorithm. Hence our $n$-amnesiac algorithm $\mathcal{B}$ goes over all possible definitions of $H_n$ and of deterministic online-LOCAL algorithms (according to an arbitrary order) until it finds this good combination. It must eventually succeed because, when the size of the input graph is fixed, there are only finitely many combinations. The proof then reduces to the previous case. See Lemma 7.6 for the formal details.

**Step 2: From component-wise algorithms to SLOCAL algorithms on rooted trees.** We heavily exploit the fact that, in rooted trees, there is a consistent orientation of the edges towards the root. We adapt results from [23, Section 7] to the SLOCAL model to show how to “cluster” a rooted tree in connected components (which are also rooted trees) in time $O(\alpha)$ and so that the following properties are met:

1. All connected components have depth $\Theta(\alpha)$.

2. All leaves of a connected component that are not at distance $\Theta(\alpha)$ from the root of the component are real leaves of the original rooted tree.

3. All other leaves are either real leaves or roots of other connected components.

The formal details can be found in Lemma 7.8.

Suppose now we are given an $n$-amnesiac (equivalently, component-wise) algorithm $\mathcal{A}$ solving an LCL $\Pi$ on rooted trees with locality $T(n)$. We briefly describe how to construct an SLOCAL algorithm $\mathcal{B}$ that solves $\Pi$ with locality $O(T(n))$ on rooted trees. Recall that in SLOCAL we may compose two algorithms with localities $T_1$ and $T_2$ and obtain an SLOCAL algorithm with locality $O(T_1 + T_2)$ [38]. Algorithm $\mathcal{B}$ is the composition of the following four algorithms with locality $O(T)$:

1. $\mathcal{B}_1$ constructs a clustering with properties 1-3 above with $\alpha = O(T)$, where the hidden constant is large enough.

2. $\mathcal{B}_2$ ensures each root of a connected component of the cluster precommits a solution in the neighborhood of the leaves of the component using $\mathcal{A}$. This can be done independently between different components if the localities are appropriately chosen. The root of the original tree also outputs a solution for itself.

3. $\mathcal{B}_3$ outputs the precommitments on the nodes designated by $\mathcal{B}_2$.

4. The fact that we used $\mathcal{A}$ independently on disjoint components of the graph (and $\mathcal{A}$ being correct) ensures that a solution to the LCL exists and the “inner part” of all connected components can be completed with a correct solution. Hence $\mathcal{B}_4$ simply brute-forces a solution inside the clusters.
Since $\Pi$ is an LCL, different components will have compatible solutions as $B_2$ precommitted a solution around leaf nodes, which are roots of other connected components.

**Step 3: From SLOCAL algorithms to LOCAL algorithms on rooted trees.** Any $o(\log n)$-time SLOCAL algorithm $\mathcal{A}$ solving an LCL over rooted trees can be turned into an $O(1)$-time SLOCAL algorithm $\mathcal{B}$ achieving the same. This is obtained by exploiting the same tree decomposition described above and providing fake, repeating identifiers to each cluster so that two equal identifiers are “far enough”. Then, we use $\mathcal{A}$ as a black-box and lie to $\mathcal{A}$ by providing the size of a cluster as the input graph size. Once we have an $O(1)$-time SLOCAL algorithm $\mathcal{B}$, how to turn it into an $O(\log^* n)$-time LOCAL algorithm is folklore.

# 3 Additional results

We will now discuss some additional results that help to establish the missing parts of the big picture in Fig. 10, and provide further intuition and examples on these models and their key properties.

## 3.1 Lower bound on 3-coloring in randomized online-LOCAL (Section 8)

So far we have connected randomized online-LOCAL with other models through simulation arguments that only work in rooted trees. Let us now put limitations on randomized online-LOCAL in a broader setting. Recall that in deterministic online-LOCAL we can 3-color bipartite graphs with locality $O(\log n)$ [2], and this is tight [22]. In Section 8 we show that randomness does not help:

**Theorem 3.1.** 3-coloring in bipartite graphs is not possible with locality $o(\log n)$ in the randomized online-LOCAL model.

This demonstrates that even though randomized online-LOCAL is a very strong model, strong enough to simulate e.g. any non-signaling distribution, it is nevertheless possible to prove strong lower bounds in this model (which then imply lower bounds across the entire landscape of models).

Here it is important to assume that the adversary is oblivious, i.e., it cannot see the random decisions of the randomized algorithm. This lower bound complements a recent result of Chang et al. [22] showing the same bound for the deterministic online-LOCAL model.

In this proof, we use the notion of a $b$-value defined in [22] as a measure of the number of incompatible boundaries present in a region of a grid. We start with the assumption that a grid can be 3-colored with locality $o(\log n)$ and derive a contradiction. The high level idea is to construct two path segments below each other, where one path segment has a large count of incompatible boundaries (a high $b$-value) and the other segment has a low boundary count (incompatible $b$-value to the upper path). This forces an algorithm to make boundaries escape on the side between the two segments. We show that the boundary count is, however, too large compared to the distance between the two segments and thus the boundaries “cannot escape”.

Two difficulties arise in the randomized case compared to the deterministic lower bound: (i) In order to create a path with a large $b$-value we have to use a probabilistic construction that produces a segment with a large $b$-value with high probability; (ii) Since the first construction is probabilistic and the adversary oblivious, we cannot “see” the large $b$-value segment constructed in (i), that is, we can neither predict its position nor its size. We therefore need to use another probabilistic construction that positions the segment in a position that forces a contradiction (and which succeeds with constant probability).
## 3.2 Deterministic dynamic-LOCAL can derandomize LOCAL (Section 9)

It is known that deterministic SLOCAL is strong enough to simulate randomized LOCAL. In Section 9 we show that the same holds also for dynamic-LOCAL, using the method of conditional expectation in a manner similar to how the result is proved for SLOCAL:

**Theorem 3.2.** *Deterministic dynamic-LOCAL can simulate randomized LOCAL.*

We also show that dynamic-LOCAL can break symmetry for free, similar to SLOCAL and the bounded-dependence model: if we can solve an LCL problem with $O(\log^* n)$ locality in LOCAL, we can solve it with $O(1)$ locality in dynamic-LOCAL.

## 3.3 Randomized online-LOCAL with adaptive adversary (Section 10)

The new model that we introduced, randomized online-LOCAL, is defined using an *oblivious* adversary. In Section 10 we show that this is also necessary: if we defined randomized online-LOCAL with an *adaptive* adversary, it would be as weak as the deterministic online-LOCAL model.

We show that an adaptive adversary in randomized online-LOCAL is so strong that a succeeding randomized online-LOCAL algorithm of locality $T$ would admit a single random-bit string that outputs a good solution for all possible graphs of a given size: hence, a correct deterministic online-LOCAL algorithm exists. Since deterministic online-LOCAL algorithms of locality $T$ for graphs of $n$ nodes are only finitely many, the deterministic online-LOCAL algorithm in its initialization phase can go over all of them until it finds the one working for all graphs of $n$ nodes: it then uses that one.

## 3.4 Randomized online-LOCAL in paths and cycles (Section 11)

Our final technical part shows that LCL problems in paths and cycles have complexity either $O(1)$ or $\Theta(n)$ in the randomized online-LOCAL model; moreover the locality is $O(1)$ in randomized online-LOCAL if and only if it is $O(\log^* n)$ in the deterministic LOCAL model. Together with prior work, this also shows that locality of an LCL problem in paths and cycles is *decidable* across all models [5] (with the caveat that we cannot distinguish between $O(1)$ and $\Theta(\log^* n)$ for quantum-LOCAL). The proof is a reworking of its deterministic variant from [2]. The main take-home message of this result is the following: cycles are not a fundamental obstacle for simulating randomized online-LOCAL in weaker models. Hence, there is hope for generalizing the simulation result of Section 7 from trees to a broader class of graphs.

## 3.5 Quantum, bounded-dependence, and non-signaling (Appendix A)

Appendix A aims at serving a dual purpose. First, it aims at formally introducing the non-signaling model based on the non-signaling principle, and at explaining *why* it is more powerful than the quantum-LOCAL model. This is not a new result, but included for completeness and to clarify the early works of Gavoille et al. [36] and Arfaoui and Fraigniaud [3]. Second, it formally introduces the bounded-dependence model based on finitely-dependent processes and argues why the relations in diagram (1) hold, and in particular why quantum-LOCAL without shared quantum state is contained not only in the non-signaling model but also in the bounded-dependence model. While all the ingredients are well-known, to our knowledge this relation between the quantum-LOCAL model and the bounded-dependence model is not made explicit in the literature before.
## 3.6 Open questions

Our work suggests a number of open questions; here are the most prominent ones:

**Question 1.** Is quantum-LOCAL stronger than randomized LOCAL for any LCL problem? In particular, is there any LCL problem with constant locality in quantum-LOCAL but super-constant locality in LOCAL? We conjecture that such a problem does not exist. Our work proves that to show this conjecture, new proof techniques are needed.

**Question 2.** Does shared global information or shared quantum state ever help with any LCL problem (beyond the fact that shared quantum state can be used to generate shared randomness, which is known to help [13])?

**Question 3.** Is it possible to simulate deterministic or randomized online-LOCAL in SLOCAL and LOCAL also in a broader graph class than rooted trees? If we could extend the result to *unrooted* trees, it would also imply new lower bounds for the widely-studied *sinkless orientation* problem [12, 16] across all models.

## 3.7 Follow-up work

Since the first versions of this work originally appeared in arXiv earlier this year, this work has already influenced at least two follow-up papers:

1. Dhar et al. [32] study the relation between online-LOCAL and deterministic LOCAL in much greater depth, especially outside the $o(\log \log \log n)$ region. It turns out that e.g. in *regular rooted trees* the complexity classes of LCL problems in randomized online-LOCAL and deterministic LOCAL exactly coincide, and as a corollary all models in Fig. 10 are exactly as strong for this graph family in the $\Omega(\log^* n)$ region.

2. Balliu et al. [13] show that there are LCL problems in which shared randomness strictly helps. This implies a number of new separations between the models in Fig. 10; for example, quantum-LOCAL with shared quantum state is strictly stronger than quantum-LOCAL without shared quantum state, the non-signaling model is strictly stronger than the bounded-dependence model, and randomized online-LOCAL is strictly stronger than randomized SLOCAL.

Put together, these papers demonstrate that especially in restricted graph classes such as trees, one can indeed often cover the entire hierarchy of models with a single theorem about randomized online-LOCAL, while in general we are dealing with a large number of genuinely distinct models.

# 4 Preliminaries

We use the notation $\mathbb{N} = \{0, 1, 2, \dots\}$ and $\mathbb{N}_+ = \mathbb{N} \setminus \{0\}$. For any positive integer $n \in \mathbb{N}_+$, we denote the set $\{1, \dots, n\}$ by $[n]$.

**Graphs.** In this work, a graph $G = (V, E)$ can be either directed ($E \subseteq V^2$) or undirected ($E \subseteq \binom{V}{2}$). If the set of nodes and the set of edges are not specified, we refer to them by $V(G)$ and $E(G)$, respectively. For any edge $e = (u, v) \in E(G)$ we say that $e$ is directed from $u$ to $v$ and is incident to $u$ and to $v$ (the latter holds also for undirected edges). All graphs in this paper are simple graphs without self-loops unless differently specified. The degree of a node $v$ is the number of edges that are incident to $v$ and is denoted by $\deg_G(v)$, or simply by $\deg(v)$ when $G$ is clear from the context. The indegree of a node $v$ is the number of directed edges that are directed towards $v$ and is denoted
by $\mathrm{indeg}_G(v)$, while the outdegree of $v$ is the number of directed edges that are incident to $v$ but
directed to some other vertex and is denoted by $\mathrm{outdeg}_G(v)$. Again, we omit the suffix $G$ if the
graph is clear from the context.

If $G$ is a subgraph of $H$, we write $G \subseteq H$. For any subset of nodes $A \subseteq V$, we denote by $G[A]$ the subgraph induced by the nodes in $A$. For any nodes $u, v \in V$, $\mathrm{dist}_G(u, v)$ denotes the distance between $u$ and $v$ in $G$ (i.e., the number of edges of any shortest path between $u$ and $v$ in $G$—it doesn't need to be a directed path); if $u$ and $v$ are disconnected, then $\mathrm{dist}_G(u, v) = +\infty$. If $G$ is clear from the context, we may also simply write $\mathrm{dist}(u, v) = \mathrm{dist}_G(u, v)$. Also, for subset of nodes $A, B \subseteq V$ and any node $v \in V$, we can define $\mathrm{dist}_G(v, A) = \min_{u \in A} \mathrm{dist}_G(u, v)$ and, by extension, $\mathrm{dist}_G(A, B) = \min_{u \in A} \mathrm{dist}_G(u, B)$. We assume that $\mathrm{dist}_G(A, \emptyset) = +\infty$. Similarly, for subgraphs $G_1, G_2 \subseteq G$, we define $\mathrm{dist}_G(G_1, G_2) = \mathrm{dist}_G(V(G_1), V(G_2))$: here, we also assume $\mathrm{dist}_G(G_1, \emptyset) = +\infty$ where $\emptyset$ is now the empty graph. For $T \in [n]$, the $T$-neighborhood of a node $u \in V$ of a graph $G$ is the set $\mathcal{N}_T(u, G) = \{v \in V \mid \mathrm{dist}_G(u, v) \le T\}$. The $T$-neighborhood of a subset $A \subseteq V$ is the set $\mathcal{N}_T(A, G) = \{v \in V \mid \exists u \in A : \mathrm{dist}_G(u, v) \le T\}$. Similarly, the $T$-neighborhood of a subgraph $H \subseteq G$ is the set $\mathcal{N}_T(H, G) = \{v \in V \mid \exists u \in V(H) : \mathrm{dist}_G(u, v) \le T\}$. If $G$ is clear from the context, we just write $\mathcal{N}_T(u), \mathcal{N}_T(A)$, and $\mathcal{N}_T(H)$. If $u \notin V$, $A \cap V = \emptyset$, or $V(H) \cap V(G) = \emptyset$, then the neighborhood $\mathcal{N}_T(u) = \emptyset$, $\mathcal{N}_T(A) = \emptyset$, or $\mathcal{N}_T(H) = \emptyset$, respectively. We make use of some graph operations: For any two graphs $G, H$, we denote by $G \cap H$ the intersection graph defined by $G \cap H = (V(G) \cap V(H), E(G) \cap E(H))$. The graph union is defined by $G \cup H = (V(G) \cup V(H), E(G) \cup E(H))$. Moreover, the graph difference is the graph $G \setminus H = (V(G) \setminus V(H), E(G) \setminus E(H))$.

Finally, for any two graphs $G$ and $H$, we write $G \sim_f H$ to denote that $G$ and $H$ are isomorphic
and $f: V(G) \to V(H)$ is an isomorphism.

**Labeling problems.** We start with the notion of labeling problem.

**Definition 4.1 (Labeling problem).** Let $\Sigma_{\mathrm{in}}$ and $\Sigma_{\mathrm{out}}$ two sets of input and output labels, respectively. A labeling problem $\Pi$ is a mapping $(G, \lambda_{\mathrm{in}}) \mapsto \{\lambda_{(\mathrm{out},i)}\}_{i \in I}$, with $I$ being a discrete set of indexes, that assigns to every graph $G$ with any input labeling $\lambda_{\mathrm{in}}: V(G) \to \Sigma_{\mathrm{in}}$ a set of permissible output vectors $\lambda_{(\mathrm{out},i)}: V(G) \to \Sigma_{\mathrm{out}}$ that might depend on $(G, \lambda_{\mathrm{in}})$. The mapping must be closed under graph isomorphism, i.e., if $\varphi: V(G) \to V(G')$ is an isomorphism between $G$ and $G'$, and $\lambda_{(\mathrm{out},i)} \in \Pi((G', \lambda_{\mathrm{in}}))$, then $\lambda_{(\mathrm{out},i)} \circ \varphi \in \Pi((G, \lambda_{\mathrm{in}} \circ \varphi))$.

A labeling problem can be thought as defined for *any* input graph of *any* number of nodes. If the set of permissible output vectors is empty for some input $(G, \lambda_{\mathrm{in}})$, we say that the problem is not solvable on the input $(G, \lambda_{\mathrm{in}})$: accordingly, the problem is solvable on the input $(G, \lambda_{\mathrm{in}})$ if $\Pi(G, \lambda_{\mathrm{in}}) \neq \emptyset$.

One observation on the generality of definition of labeling problem follows: one can actually
consider problems that require to output labels on edges.

We actually focus on labeling problems where, for any input graph, an output vector $\lambda_{\mathrm{out}}$ is permissible if and only if the restrictions of the problem on any local neighborhoods can be solved and there exist compatible local permissible output vectors whose combination provides $\lambda_{\mathrm{out}}$. This concept is grasped by the notion of locally checkable labeling (LCL) problems, first introduced by Naor and Stockmeyer [57]. For any function $f: A \to B$ and any subset $A' \subseteq A$, let us denote the restriction of $f$ to $A'$ by $f|_{A'}$. Furthermore, we define a centered graph to be a pair $(H, v_H)$ where $H$ is a graph and $v_H \in V(H)$ is a vertex of $H$ that we name the *center* of $H$. The *radius* of a centered graph is the maximum distance from $v_H$ to any other node in $H$.

**Definition 4.2 (Locally checkable labeling problem).** Let $r, \Delta \in \mathbb{N}$. Let $\Sigma_{\mathrm{in}}$ and $\Sigma_{\mathrm{out}}$ two finite sets of input and output labels, respectively, and $\Pi$ a labeling problem. $\Pi$ is locally checkable with
checking radius $r$ if there exists a family $\mathcal{S} = \{((H, v_H), \bar{\lambda}_{in}, \bar{\lambda}_{out})_i\}_{i \in I}$ of tuples, where $(H, v_H)$ is a centered graph of radius at most $r$ and maximum degree at most $\Delta$, $\bar{\lambda}_{in}: V(H) \to \Sigma_{in}$ is an input labeling for $H$, $\bar{\lambda}_{out}: V(H) \to \Sigma_{out}$ is an output labeling for $H$ (which can depend on $\bar{\lambda}_{in}$) with the following property

* for any input $(G, \lambda_{in})$ to $\Pi$ with $\deg(G) \le \Delta$, an output vector $\lambda_{out}: V(G) \to \Sigma_{out}$ is permissible (i.e., $\lambda_{out} \in \Pi((G, \lambda_{in}))$) if and only if, for each node $v \in V(G)$, the tuple $((G[N_r(v)]), \lambda_{in}|_{N_r(v)}, \lambda_{out}|_{N_r(v)})$ belongs to $\mathcal{S}$ (up to graph isomorphisms).

Notice that the family $\mathcal{S}$ can be always thought to be finite up to graph isomorphisms, as $r$ and $\Delta$ are fixed and the set of input/output labels are finite. We now define the computational models we work in.

**The port-numbering model.** A port-numbered network is a triple $N = (V, P, p)$ where $V$ is the set of nodes, $P$ is the set of ports, and $p: P \to P$ is a function specifying connections between ports. Each element $x \in P$ is a pair $(v, i)$ where $v \in V$, $i \in \mathbb{N}_+$. The connection function $p$ between ports is an involution, that is, $p(p(x)) = x$ for all $x \in P$. If $(v, i) \in P$, we say that $(v, i)$ is port number $i$ in node $v$. The degree of a node $v$ in the network $N$ is $\deg_N(v)$ is the number of ports in $v$, that is, $\deg_N(v) = |\{i \in \mathbb{N} : (v, i) \in P\}|$. Unless otherwise mentioned, we assume that port numbers are consecutive, i.e., the ports of any node $v \in V$ are $(v, 1), \dots, (v, \deg_N(v))$. Clearly, a port-numbered network identifies an *underlying graph* $G = (V, E)$ where, for any two nodes $u, v \in V$, $\{u, v\} \in E$ if and only if there exists ports $x_u, x_v \in P$ such that $p(x_u) = x_v$. Clearly, the degree of a node $\deg_N(v)$ corresponds to $\deg_G(v)$.

In the port-numbering model we are given distributed system consisting of a port-numbered network of $|V| = n$ processors (or nodes) that operates in a sequence of synchronous rounds. In each round the processors may perform unbounded computations on their respective local state variables and subsequently exchange of messages of arbitrary size along the links given by the underlying input graph. Nodes identify their neighbors by using ports as defined before, where port assignment may be done adversarially. Barring their degree, all nodes are identical and operate according to the same local computation procedures. Initially all local state variables have the same value for all processors; the sole exception is a distinguished local variable $x(v)$ of each processor $v$ that encodes input data.

Let $\Sigma_{in}$ be a set of input labels. The input of a problem is defined in the form of a labeled graph $(G, x)$ where $G = (V, E)$ is the system graph, $V$ is the set of processors (hence it is specified as part of the input), and $x: V \to \Sigma_{in}$ is an assignment of an input label $\lambda_{in}(v) \in \Sigma_{in}$ to each processor $v$. The output of the algorithm is given in the form of a vector of local output labels $\lambda_{out}: V \to \Sigma_{out}$, and the algorithm is assumed to terminate once all labels $\lambda_{out}(v)$ are definitely fixed. We assume that nodes and their links are fault-free. The local computation procedures may be randomized by giving each processor access to its own set of random variables; in this case, we are in the *randomized port-numbering model* as opposed to the *deterministic* port-numbering model.

The running time of an algorithm is the number of synchronous rounds required by all nodes to produce output labels. If an algorithm running time is $T$, we also say that the algorithm has locality $T$. Notice that $T$ can be a function of the size of the input graph. We say that a problem $\Pi$ over some graph family $\mathcal{F}$ has complexity $T$ in the port-numbering model if there is a port-numbering algorithm running in time $T$ that solves $\Pi$ over $\mathcal{F}$, and $T = T(n)$ is the minimum running time (among all possible algorithms that solve $\Pi$ over $\mathcal{F}$) in the worst case instance of size $n$. If the algorithm is randomized, we also require that the failure probability is at most $1/n$, where $n$ is the size of the input graph.
We remark that the notion of an (LCL) problem is a graph problem, and does not depend on
the specific model of computation we consider (hence, the problem cannot depend on, e.g., port
numbers).

**The LOCAL model.** The LOCAL model was first introduced by Linial [53]: it is just the port-
numbering model augmented with an assignment of unique identifiers to nodes. Let $c \ge 1$ be a
constant, and let $\Sigma_{\text{in}}$ be a set of input labels. The input of a problem is defined in the form of a
labeled graph $(G, x)$ where $G = (V, E)$ is the system graph, $V$ is the set of processors (hence it
is specified as part of the input), and $x: V \to [n^c] \times \Sigma_{\text{in}}$ is an assignment of a *unique* identifier
$\text{id}(v) \in [n^c]$ and of an input label $\lambda_{\text{in}}(v) \in \Sigma_{\text{in}}$ to each processor $v$. The output of the algorithm is
given in the form of a vector of local output labels $\lambda_{\text{out}}: V \to \Sigma_{\text{out}}$, and the algorithm is assumed
to terminate once all labels $\lambda_{\text{out}}(v)$ are definitely fixed. We assume that nodes and their links are
fault-free. The local computation procedures may be randomized by giving each processor access to
its own set of random variables; in this case, we are in the *randomized LOCAL* (randomized LOCAL) model as opposed to *deterministic LOCAL* (deterministic LOCAL). Notice that the knowledge of $n$
makes the randomized port-numbering model roughly equivalent to the randomized LOCAL model,
as unique identifiers can be produced with high probability. We say that a problem $\Pi$ over some
graph family $\mathcal{F}$ has complexity $T$ in the LOCAL model if there is a LOCAL algorithm running in time
$T$ that solves $\Pi$ over $\mathcal{F}$, and $T = T(n)$ is the minimum running time (among all possible algorithms
that solve $\Pi$ over $\mathcal{F}$) in the worst case instance of size $n$. If the algorithm is randomized, we also
require that the failure probability is at most $1/n$, where $n$ is the size of the input graph.

**The sequential LOCAL model.** The sequential LOCAL model was first introduced by [38]: it is a sequential version of the LOCAL model. Nodes are processed according to an adversarial order $\sigma = v_1, \dots, v_n$. When processing a node $v_i$, a $T$-round algorithm collects all inputs in the radius-$T$ neighborhood of $v_i$ (including the states and the outputs of previously processed nodes in $N_T(V_i)$, i.e., $v_j \in N_T(V_i)$ for $j < i$): we say that such an algorithm has complexity $T$. Note that the algorithm might store all inputs in $N_T(v_i)$ in the state of $v_i$: hence, when processing $v_i$, it can see the input of $v_j$, $j < i$, if and only if there is a subsequence of nodes $\{v_{h_k}\}_{k \in [m]}$ with $j = h_k < h_{k+1} < \dots < h_{k_m} = i$ such that $v_{h_k} \in N_T(v_{h_{k+1}})$ for all $k \in [m]$.

If the algorithm is given an infinite random bit string, we talk about the randomized SLOCAL model, as opposed to the deterministic SLOCAL model. We assume that the adversarial order according to which nodes are processed is oblivious to the random bit string, as in the original definition of the model. We say that a problem $\Pi$ over some graph family $\mathcal{F}$ has complexity $T$ in the SLOCAL model if there is an SLOCAL algorithm running in time $T$ that solves $\Pi$ over $\mathcal{F}$, and $T = T(n)$ is the minimum running time (among all possible algorithms that solve $\Pi$ over $\mathcal{F}$) in the worst case instance of size $n$. If the algorithm is randomized, we also require that the failure probability is at most $1/n$, where $n$ is the size of the input graph.

**The dynamic-LOCAL model.** The deterministic dynamic-LOCAL was introduced in [2]. It is a centralized model of computing where the adversary constructs the graph one edge at a time. An adversary construct the input graph by adding one edge at a time (with an ordering of the nodes). The algorithm has a global view of the current state of the graph and has to commit for the newly added nodes (according to the ordering), but it has to maintain a feasible solution after each update. The algorithm is restricted so that after a modification at node $v$, it can only update the solution within distance $T(n)$ from $v$. We say that a problem $\Pi$ over some graph family $\mathcal{F}$ has complexity $T(n)$ in the dynamic-LOCAL model if $T(n)$ is the minimum function such that there
is a dynamic-LOCAL algorithm running in time $T(n)$ that solves $\Pi$ over $\mathcal{F}$, and $T = T(n)$ is the minimum running time (among all possible algorithms that solve $\Pi$ over $\mathcal{F}$) in the worst case instance of size $n$.

**The online-LOCAL model.** The (deterministic) online-LOCAL model was introduced in [2]. It is basically equivalent to the SLOCAL model with global memory. More specifically, the online-LOCAL model is a centralized model of computing where the algorithm initially knows only the set of nodes of the input graph $G$. The nodes are processed with respect to an adversarial input sequence $\sigma = v_1, v_2, \dots, v_n$. The output of $v_i$ depends on $G_i = G[\cup_{j=1}^i \mathcal{N}_T(v_j)]$, i.e., the subgraph induced by the radius-$T$ neighborhoods of $v_1, v_2, \dots, v_i$ (including all input data), plus all the outputs of previously processed nodes (in order).

We define the randomized online-LOCAL model as a randomized variant of the online-LOCAL model where the label assigned by the algorithm to $v_i$ is a random outcome. Note that this model is oblivious to the randomness used by the algorithm. In particular this means that the graph $G \setminus G_i$ cannot be changed depending on the label assigned to $v_i$. One could also define the randomized online-LOCAL model in an adaptive manner, but it turns out that this is equivalent to the deterministic online-LOCAL model as we show in Section 10. We say that a problem $\Pi$ over some graph family $\mathcal{F}$ has complexity $T$ in the online-LOCAL (randomized online-LOCAL) model if there is an online-LOCAL (randomized online-LOCAL) algorithm running in time $T$ that solves $\Pi$ over $\mathcal{F}$, and $T = T(n)$ is the minimum running time (among all possible algorithms that solve $\Pi$ over $\mathcal{F}$) in the worst case instance of size $n$. If the algorithm is randomized, we also require that the failure probability is at most $1/n$, where $n$ is the size of the input graph.

# 5 Simulating non-signaling in randomized online-LOCAL

## 5.1 Framework

In this section we give the necessary framework to define the non-signaling model and is largely inspired by the definitions given in [27, 36]. Next definition introduces the concept of outcome.

**Definition 5.1 (Outcome).** Let $\Sigma_{in}$ and $\Sigma_{out}$ be two sets of input and output labels, respectively, and let $\mathcal{F}$ be a family of graphs. An outcome $O$ over $\mathcal{F}$ is a mapping $(G, x) \mapsto \{(\lambda_{(out,i)}, p_i)\}_{i \in I}$, with $I$ being a discrete set of indexes, assigning to every input graph $G \in \mathcal{F}$ with any input data $x = (\text{id} : V(G) \to [|V(G)|^c], \lambda_{in} : V(G) \to \Sigma_{in})$, a discrete probability distribution $\{p_i\}_{i \in I}$ over output vectors $\lambda_{(out,i)} : V(G) \to \Sigma_{out}$ such that:

1. for all $i \in I$, $p_i > 0$;

2. $\sum_{i \in I} p_i = 1$;

3. $p_i$ represents the probability of obtaining $\lambda_{(out,i)}$ as the output vector of the distributed system.

We say that an outcome $O$ over some graph family $\mathcal{F}$ solves problem $\Pi$ over $\mathcal{F}$ with probability $p$ if, for every $G \in \mathcal{F}$ and any input data $x = (\text{id}, \lambda_{in})$, it holds that

$$ \sum_{\substack{(\lambda_{(out,i)}, p_i) \in O((G,x)) : \\ \lambda_{(out,i)} \in \Pi((G, \lambda_{in}))}} p_i \geq p. $$

When $p=1$, we will just say that $O$ solves problem $\Pi$ over the graph family $\mathcal{F}$.

The next computational model tries to capture the fundamental properties of any physical computational model (in which one can run either deterministic, random, or quantum algorithms)
that respects causality. The defining property of such a model is that, for any two (labeled) graphs $(G_1, x_1)$ and $(G_2, x_2)$ that share some identical subgraph $(H, y)$, every node $u$ in $H$ must exhibit identical behavior in $G_1$ and $G_2$ as long as its local view, that is, the set of nodes up to distance $T$ away from $u$ together with input data and port numbering, is fully contained in $H$. As the port numbering can be computed with one round of communication through a fixed procedure (e.g., assigning port numbers 1, 2, ..., deg($v$) based on neighbor identifiers in ascending order) and we care about asymptotic bounds, we will omit port numbering from the definition of local view.

The model we consider has been introduced by [36]. In order to proceed, we first define the non-signaling property of an outcome. Let $T \ge 0$ be an integer, and $I$ a set of indices. For any set of nodes $V$, subset $S \subseteq V$, and for any input $(G = (V, E), x)$, we define its T-local view as the set

$$v_T(G, x, S) = \{(u, x(u)) \mid \exists u \in V, v \in S \text{ such that } \text{dist}_G(u, v) \le T\},$$

where $\text{dist}_G(u, v)$ is the distance in $G$. Furthermore, for any subset of nodes $S \subseteq V$ and any output distribution $\{\lambda_{(\text{out},i)}, p_i\}_{i \in I}$, we define the marginal distribution of $\{\lambda_{(\text{out},i)}, p_i\}_{i \in I}$ on set $S$ as the unique output distribution defined as follows: for any $\lambda_{\text{out}}: V(G) \to \Sigma_{\text{out}}$, the probability of $\lambda_{\text{out}}|_S$ on $S$ is given by

$$p(\lambda_{\text{out}}, S) = \sum_{i \in I : \lambda_{\text{out}}|_S = \lambda_{(\text{out},i)}|_S} p_i,$$

where $\lambda_{\text{out}}|_S$ and $\lambda_{(\text{out},i)}|_S$ are the restrictions of $\lambda_{\text{out}}$ and $\lambda_{(\text{out},i)}$ on $S$, respectively.

**Definition 5.2 (Non-signaling outcome).** Let $\mathcal{F}$ be a family of graphs. An outcome $O: (G, x) \mapsto \{(\lambda_{(\text{out},i)}, p_i)\}_{i \in I}$ over $\mathcal{F}$ is non-signaling beyond distance $T = T(G, x)$ if for any pair of inputs $(G_1 = (V_1, E_1), x_1)$, $(G_2 = (V_2, E_2), x_2)$, with the same number of nodes, such that $v_{T(G_1, x_1)}(G_1, x_1, S)$ is isomorphic to $v_{T(G_1, x_1)}(G_2, x_2, S)$ and $G_1, G_2 \in \mathcal{F}$, the output distributions corresponding to these inputs have identical marginal distributions on the set $S$.

Definition 5.2 is also the more general definition for the locality of an outcome: an outcome $O$ has locality $T$ if it is non-signaling beyond distance $T$.

**The $\varphi$-LOCAL model.** The $\varphi$-LOCAL model is a computational model that produces non-signaling outcomes over some family of graphs $\mathcal{F}$. Let $p \in [0, 1]$. A problem $\Pi$ over some graph family $\mathcal{F}$ has complexity $T$ (and success probability $p$) if there exists an outcome $O$ that is non-signaling beyond distance $T$ which solves $\Pi$ over $\mathcal{F}$ (with probability at least $p$), and $T = T(n)$ is the minimum “non-signaling distance” (among all possible outcomes that solve $\Pi$ over $\mathcal{F}$) in the worst case instance of size $n$.

As every (deterministic or randomized) algorithm running in time at most $T$ in the LOCAL model produces an outcome which has locality $T$, we can provide lower bounds for the LOCAL model by proving them in the $\varphi$-LOCAL model.

Notice that algorithms in the LOCAL model can be always thought as producing outputs for any input graph: when the computation at any round is not defined for some node, we can make the node output some garbage label, say $\perp$. If we require that also outcomes are defined for every possible graph, then we are restricting the power of $\varphi$-LOCAL because outcomes must be defined accordingly. This gives rise to a slightly weaker model, the non-signaling model, which was considered in other works such as [27] and is still stronger than any classical or quantum variation of the LOCAL model.

**Theorem 5.3.** Let $\Pi$ be any LCL problem over any family of graphs $\mathcal{F}$. Let $O: (G, \lambda_{in}) \mapsto \{(\lambda_{(\text{out},h)}, p_i)\}_{h \in H}$ be an outcome over $\mathcal{F}$ which solves $\Pi$ with failure probability at most $\varepsilon$ and is non-signaling at distance greater than $T$. There exists a randomized online-LOCAL algorithm $\mathcal{A}$ with complexity $T$ that solves $\Pi$ over $\mathcal{F}$ and has failure probability at most $\varepsilon$.
We want to design a randomized online-LOCAL algorithm A with complexity T that solves Π over F and has failure probability at most ε that somehow simulates O. We need to assume that the number of nodes of the input graph is known by A.

Fix any graph G ∈ F of n nodes and any input labeling λ<sub>in</sub>, and fix any sequence of nodes v<sub>1</sub>, . . . , v<sub>n</sub> the adversary might choose to reveal to the algorithm.

The adversary initially shows G[ N<sub>T</sub>(v<sub>1</sub>)] to the algorithm (including input labels and identifiers) and asks it to label v<sub>1</sub>. In order for the algorithm to choose an appropriate output, it can arbitrarily choose a graph H<sub>1</sub> ∈ F with n nodes that contains a subgraph isomorphic to G[ N<sub>T</sub>(v<sub>1</sub>)] (again, including input labels and identifiers). Notice that H<sub>1</sub> necessarily exists since G itself is such a graph. We stress that the arbitrariness in the choice of H<sub>1</sub> is thanks to the non-signaling property, which ensures that the restriction of the output distribution O(H<sub>1</sub>, λ<sub>in</sub>) over N<sub>T</sub>(v<sub>1</sub>) does not change if the topology of the graph outside G[ N<sub>T</sub>(v<sub>1</sub>)] differs (i.e., no matter how the adversary chooses it). Indeed, if O did not have the non-signaling property, then it would be impossible to sample from it correctly since the marginal output distribution on G[ N<sub>T</sub>(v<sub>1</sub>)] would depend on the topology of the graph beyond it, which the algorithm still has no knowledge of.

For any λ<sub>out</sub> : V(G) → Σ<sub>out</sub>, the probability that A labels v<sub>1</sub> with λ<sub>out</sub>(v<sub>1</sub>) is

$$
p(\lambda_{\text{out}}, v_1) = \sum_{k: \lambda_{\text{out}} \upharpoonright \{v_1\} = \lambda_{(\text{out}, k)} \upharpoonright \{v_1\}} p_k,
$$

$$
\text{where } \{(\lambda_{(\text{out},k)}, p_k)\}_{k \in K_1} = \mathcal{O}(H_1, \lambda_{\text{in}}).
$$

Let Λ<sub>i</sub> be the random variable yielding the label assigned to v<sub>i</sub> by A. In general, for any λ<sub>out</sub> : V(G) → Σ<sub>out</sub> let p(λ<sub>out</sub>, v<sub>i</sub>) denote the probability that Λ<sub>i</sub> = λ<sub>out</sub>(v<sub>i</sub>). Assume now that G[ N<sub>T</sub>(v<sub>i+1</sub>)] is shown to the algorithm. Conditional on Λ<sub>1</sub>, . . . , Λ<sub>i</sub>, for any λ<sub>out</sub> : V(G) → Σ<sub>out</sub> such that λ<sub>out</sub>(v<sub>j</sub>) = Λ<sub>j</sub> for all j = 1, . . . , i, the probability that Λ<sub>i+1</sub> = λ<sub>out</sub>(v<sub>i+1</sub>) is

$$
p(\lambda_{\text{out}}, v_{i+1}) = \sum_{\substack{k: \lambda_{\text{out}} \upharpoonright \{v_j\} = \lambda_{(\text{out}, k)} \upharpoonright \{v_j\} \\ \forall 1 \le j \le i+1}} \frac{p_k}{\prod_{1 \le l \le i} p(\lambda_{\text{out}}, v_l)},
$$

where { (λ<sub>(out,k)</sub> , p<sub>k</sub> ) }<sub>k ∈ K<sub>i+1</sub></sub> = O( H<sub>i+1</sub> , λ<sub>in</sub> ) for any graph H<sub>i+1</sub> ∈ F of n nodes that contains a subgraph isomorphic to G[ ⋃<sub>i=1</sub><sup>i+1</sup> N<sub>T</sub>( v<sub>j</sub> )] (including input labels and identifiers). As before, H<sub>i+1</sub> may be chosen arbitrarily due to the non-signaling property.

Now consider O(G, λ<sub>in</sub>) = { (λ<sub>(out,h)</sub> , p<sub>h</sub> ) }<sub>h ∈ H</sub> for the right input graph G, and take any

$$
(\lambda_{(\text{out},h^*)}, p_{h^*}) \in \mathcal{O}(G, \lambda_{\text{in}}).
$$

The probability that the outcomes of Λ<sub>1</sub>, . . . , Λ<sub>n</sub> give exactly λ<sub>(out,h<sup>\*</sup>)</sub> is

$$
\begin{align*}
& \Pr[\Lambda_1 = \lambda_{(\text{out},h^*)}(v_1), \dots, \Lambda_n = \lambda_{(\text{out},h^*)}(v_n)] \\
& = \Pr[\Lambda_n = \lambda_{(\text{out},h^*)}(v_n) | \Lambda_1 = \lambda_{(\text{out},h^*)}(v_1), \dots, \Lambda_{n-1} = \lambda_{(\text{out},h^*)}(v_{n-1})] \\
& \quad \cdot \Pr[\Lambda_{n-1} = \lambda_{(\text{out},h^*)}(v_{n-1}) | \Lambda_1 = \lambda_{(\text{out},h^*)}(v_1), \dots, \Lambda_{n-2} = \lambda_{(\text{out},h^*)}(v_{n-2})] \\
& \dots \\
& \quad \cdot \Pr[\Lambda_1 = \lambda_{(\text{out},h^*)}(v_1)] \\
& = p(\lambda_{(\text{out},h^*)}, v_1) \cdots p(\lambda_{(\text{out},h^*)}, v_n) \\
& = \prod_{1 \le l \le n-1} p(\lambda_{\text{out}}, v_l) \cdot \sum_{\substack{k_n: \lambda_{(\text{out},h^*)} \upharpoonright \{v_j\} = \lambda_{(\text{out},k_j)} \upharpoonright \{v_j\} \\ \forall 1 \le j \le n}} \frac{p_{k_n}}{\prod_{1 \le l \le n-1} p(\lambda_{\text{out}}, v_l)}
\end{align*}
$$
$$ = \sum_{\substack{k_n: \lambda_{(\text{out},h^*)} \upharpoonright_{\{v_j\}} = \lambda_{(\text{out},k_j)} \upharpoonright_{\{v_j\}} \\ \forall 1 \le j \le n}} p_{k_n}. $$

Notice that

$$ \sum_{\substack{k_n: \lambda_{(\text{out},h^*)} \upharpoonright_{\{v_j\}} = \lambda_{(\text{out},k_j)} \upharpoonright_{\{v_j\}} \\ \forall 1 \le j \le n}} p_{k_n} = p_{h^*} $$

as $H_n$ is necessarily isomorphic to $G$. By the hypothesis,

$$ \sum_{h: \lambda_{(\text{out},h)} \text{ is valid for } (G, \lambda_{\text{in}})} p_h \ge 1 - \varepsilon, $$

implying that $\mathcal{A}$ succeeds with probability at least $1 - \varepsilon$.

# 6 Bounded-dependence model can break symmetry

For any graph $G = (V, E)$, a random process (or distribution) on the vertices of $G$ is a family of random variables $\{X_v\}_{v \in V}$, indexed by $V$, while a random process on the edges of $G$ is a family of random variables $\{X_e\}_{e \in E}$ indexed by $E$. More generally, a random process on $G$ is a family of random variables $\{X_y\}_{y \in V \cup E}$ indexed by $V \cup E$. The variables of a random process live in the same probability space and take values in some label set $\Sigma$. In general, we will consider random processes over vertices of graphs unless otherwise specified.

We now introduce the notion of $T$-dependent distribution. To do so, we extend the definition of distance to edges as follows: For any two edges $e = \{v_1, v_2\}$, $e' = \{u_1, u_2\} \in E$, $\text{dist}_G(e, e') = \min_{i,j \in [2]} \text{dist}_G(v_i, u_j)$. Similarly, the distance between any edge $e = (v_1, v_2)$ and a vertex $v$ is $\text{dist}_G(e, v) = \min_{i \in [2]} \text{dist}_G(v_i, v)$. The definition extends easily to subsets containing vertices and edges.

**Definition 6.1 (T-dependent distribution).** Let $T \in \mathbb{N}$ be a natural number and $G = (V, E)$ be any graph. A random process $\{X_v\}_{v \in V}$ on the vertices $G$ is said to be a $T$-dependent distribution if, for all subsets $S, S' \subseteq V$ such that $\text{dist}_G(S, S') > T$, the two processes $\{X_v\}_{v \in S}$ and $\{X_v\}_{v \in S'}$ are independent. Analogous definitions hold for random processes on the edges of a graph and for random processes on the whole graph.

A way to define $T$-dependent distributions that uses the same notation of Section 5.1 is by describing the output probability of global labelings: Let $I$ be a discrete set of indices, and $G = (V, E)$ some graph. A distribution $\{(\lambda_i, p_i)\}_{i \in I}$ over output labelings, where $\lambda_i : V \to \Sigma$ is an output labeling, is $T$-dependent if the following holds: for all output labelings $\lambda$ in $\{(\lambda_i, p_i)\}$, for every two subsets of nodes $S_1, S_2 \subseteq V(G)$ such that $\text{dist}_G(S_1, S_2) > T$, we have that

$$ p(\lambda, S_1 \cup S_2) = p(\lambda, S_1) \cdot p(\lambda, S_2). $$

Notice that outcomes, as defined in Definition 5.1, output a random process for every input. Often, we have a family of graphs of arbitrarily large size $n$ on which a $T(n)$-dependent distribution is defined.<fnref n="1" />

Now we define the hypothetical computational model that outputs $T$-dependent distributions on some input graph.

<footnote n="1">¹Note that the dependency $T$ might depend on other graph parameters such as the maximum degree $\Delta$, the chromatic number $\chi$, etc.</footnote>
**The bounded-dependence model.** The bounded-dependence model is a computational model that, for a given family of graphs $\mathcal{F}$, produces an outcome (as defined in Definition 5.1) over $\mathcal{F}$ that is non-signaling beyond distance $T = T(G, x)$ (as defined in Definition 5.2), where $G \in \mathcal{F}$ and $x$ represents the input, which, in turn, produces $T(G, x)$-dependent distributions. The random processes produced by an outcome are said to be finitely-dependent if $T = O(1)$ for all graphs in $\mathcal{F}$ and all input data. If an outcome with the aforementioned properties solves a problem $\Pi$ over a graph family $\mathcal{F}$ with probability at least $p$, we say that the pair $(\Pi, \mathcal{F})$ has complexity $T$ (with success probability $p$), and $T = T(n)$ is the minimum dependence (among all possible distributions solving $\Pi$ over $\mathcal{F}$) in the worst case instance of size $n$. We remark that $T$ is also called the *locality* or the *complexity* of the corresponding output distributions.

We are particularly interested in $T$-dependent distributions that satisfy invariance properties: We say that a random process $\{X_v\}_{v \in V}$ over vertices of a graph $G = (V, E)$ is invariant under automorphisms if, for all automorphisms $f: V \to V$ of $G = (V, E)$, the two processes $\{X_v\}_{v \in V}$ and $\{Y_v = X_{f(v)}\}_{v \in V}$ are equal in law. The definition is easily extendable to random processes on edges and random processes on the whole graph.

A stronger requirement is the *invariance under subgraph isomorphism*: Suppose we have an outcome $O: (G, x) \mapsto \{X_v\}_{v \in V(G)}$ that maps each input graph $G$ from family of graphs $\mathcal{F}$ and any input data $x$ to a $T = T(G, x)$-dependent distribution over $G$ from a family of random process $\mathcal{R}$. We say that the random process over vertices in $\mathcal{R}$ are invariant under subgraph isomorphisms if, given any two graphs $G_1, G_2 \in \mathcal{F}$ of size $n_1, n_2$ with associated process $\{X_v^{(1)}\}_{v \in V(G_1)}$ and $\{X_v^{(2)}\}_{v \in V(G_2)}$, and any two subgraphs $H_1 \subseteq G_1, H_2 \subseteq G_2$ such that $G_1[\mathcal{N}_{T(n_1)}(H_1)]$ and $G_2[\mathcal{N}_{T(n_2)}(H_2)]$ are isomorphic (with the isomorphism that brings $H_1$ into $H_2$), then $\{X_v^{(1)}\}_{v \in V(H_1)}$ and $\{X_v^{(2)}\}_{v \in V(H_2)}$ are equal in law.<fnref n="2" /> Trivially, invariance under subgraph isomorphisms implies invariance under automorphisms and the non-signaling property. This definition is again easily extendable to the case of families of random processes over edges or over graphs in general.

The baseline of our result is a finitely-dependent distribution provided by [45, 47] on paths and cycles.

**Theorem 6.2** (Finitely-dependent coloring of the integers and of cycles [45, 47]). Let $G = (V, E)$ be a graph that is either a cycle with at least 2 nodes or has $V = \mathbb{Z}$ and $E = \{(i, i+1) : i \in \mathbb{Z}\}$. For $(k, q) \in \{(1, 4), (2, 3)\}$, there exists a $k$-dependent distribution $\{X_v^{(G)}\}_{v \in V(G)}$ that gives a $q$-coloring of $G$. Furthermore, such distributions can be chosen to meet the following properties: If $\{X_i\}_{i \in [n]}$ is the $k$-dependent $q$-coloring of the $n$-cycle and $\{Y_i\}_{i \in \mathbb{Z}}$ is the $k$-dependent $q$-coloring of the integers, then $\{X_i\}_{i \in [n-k]}$ is equal in law to $\{Y_i\}_{i \in [n-k]}$. If $n = 2$, then the finitely-dependent colorings on the 2-cycle and on a path of 2 nodes are identical in distribution.

It is immediate that the disjoint union of any number of paths and cycles (even countably many) admits such distributions as well.

**Corollary 6.3.** Let $\mathcal{F}$ be the family of graphs formed by the disjoint union (possibly uncountably many) paths with countably many nodes and cycles of any finite length. For all $G \in \mathcal{F}$ and for $(k, q) \in \{(1, 4), (2, 3)\}$, there exists a $k$-dependent distribution $\{X_v^{(G)}\}_{v \in V(G)}$ that gives a $q$-coloring of $G$. Furthermore, such distributions can be chosen to meet all the following properties:

1. On each connected component $H \subseteq G$, $\{X_v^{(G)}\}_{v \in V(H)}$ is given by Theorem 6.2.

2. $\{\{X_v^{(G)}\}_{v \in V(G)}\}_{G \in \mathcal{F}}$ is invariant under subgraph isomorphisms.

<footnote n="2">²We remark that, as opposed to Definition 5.2, the isomorphism must preserve the input but *not* the node identifiers.</footnote>
We will use this result to provide “fake local identifiers” to the nodes of the graph to simulate an $O(\log^* n)$-round LOCAL algorithm through a random process with constant dependency. In order to do that, we introduce some results on the composition of T-dependent distributions.

Trivially, every T-round (deterministic or randomized) port-numbering algorithm defines a 2T-dependent distribution over the input graph. Furthermore, if the underlying port-numbering model has access to random bits, the distribution can be made invariant under subgraph isomorphisms (provided that, whenever a distribution over input labelings is given together with the input graph, such distribution is also invariant under subgraph isomorphisms). The composition of the $T_2$-dependent distribution obtained by a $T_2$-round port-numbering algorithm and any $T_1$-dependent distribution yields a $(2T_2 + T_1)$-dependent distribution.

**Lemma 6.4.** Let $\Sigma^{(1)}$ and $\Sigma^{(2)}$ be two label sets with countably many labels. Let $\mathcal{F}$ be any family of graphs, and let $\mathcal{R} = \{\{X_v\}_{v \in V(G)} : G \in \mathcal{F}\}$ be a family of $T_1$-dependent distributions taking values in $\Sigma^{(1)}$, where $T_1$ might depend on parameters of $G$. Consider any $T_2$-round port-numbering algorithm $\mathcal{A}$ that takes as an input $G \in \mathcal{F}$ labelled by $\{X_v\}_{v \in V(G)}$: it defines another distribution $\{Y_v\}_{v \in V(G)}$ taking values in some label set $\Sigma^{(2)}$. Then, the following properties hold:

1. $\{Y_v\}_{v \in V(G)}$ is a $(2T_2 + T_1)$-dependent distribution on $G$.

2. If the processes in $\mathcal{R}$ are invariant under subgraph isomorphisms, $T_2$ is constant, and $\mathcal{A}$ does not depend on the size of the input graph and permutes port numbers locally u.a.r. at round 0, then the processes in $\{\{Y_v\}_{v \in V(G)} : G \in \mathcal{F}\}$ are invariant under subgraph isomorphisms.

*Proof.* We prove the claim 1 first. Fix any $G = (V, E) \in \mathcal{F}$, and the corresponding $T_2$-dependent distribution $\{X_v\}_{v \in V} \in \mathcal{R}$. Fix any two subsets $S, S' \subseteq V$ such that $\text{dist}_G(S, S') > 2T_2 + T_1$. Consider any output labeling $\lambda^{(2)} : V \to \Sigma^{(2)}$. Then,

$$
\begin{align}
& \mathrm{Pr} \left[ \bigcap_{v \in S \cup S'} \{Y_v = \lambda^{(2)}(v)\} \right] \nonumber \\
& = \sum_{\lambda^{(1)} : V \to \Sigma^{(1)}} \mathrm{Pr} \left[ \bigcap_{v \in S \cup S'} \{Y_v = \lambda^{(2)}(v)\} \middle| \bigcap_{v \in V} \{X_v = \lambda^{(1)}(v)\} \right] \nonumber \\
& \quad \cdot \mathrm{Pr} \left[ \bigcap_{v \in V} \{X_v = \lambda^{(1)}(v)\} \right] \nonumber \\
& = \sum_{\lambda^{(1)} : V \to \Sigma^{(1)}} \mathrm{Pr} \left[ \bigcap_{v \in S \cup S'} \{Y_v = \lambda^{(2)}(v)\} \middle| \bigcap_{v \in \mathcal{N}_{T_2(S \cup S')}} \{X_v = \lambda^{(1)}(v)\} \right] \tag{3} \\
& \quad \cdot \mathrm{Pr} \left[ \bigcap_{v \in V} \{X_v = \lambda^{(1)}(v)\} \right] \nonumber \\
& = \sum_{\lambda^{(1)} : \mathcal{N}_{T_2}(S \cup S') \to \Sigma^{(1)}} \mathrm{Pr} \left[ \bigcap_{v \in S \cup S'} \{Y_v = \lambda^{(2)}(v)\} \middle| \bigcap_{v \in \mathcal{N}_{T_2(S \cup S')}} \{X_v = \lambda^{(1)}(v)\} \right] \nonumber \\
& \quad \cdot \mathrm{Pr} \left[ \bigcap_{v \in \mathcal{N}_{T_2}(S \cup S')} \{X_v = \lambda^{(1)}(v)\} \right], \nonumber
\end{align}
$$

where Eq. (3) holds because the output of $\{Y_v\}_{v \in S \cup S'}$ is independent of $\{X_v\}_{v \notin \mathcal{N}_{T_2}(S \cup S')}$. Since $\text{dist}_G(S, S') > 2T_2$,

$$
\sum_{\lambda^{(1)}: \mathcal{N}_{T_2}(S \cup S') \to \Sigma^{(1)}} \mathrm{Pr} \left[ \bigcap_{v \in S \cup S'} \{Y_v = \lambda^{(2)}(v)\} \middle| \bigcap_{v \in \mathcal{N}_{T_2}(S \cup S')} \{X_v = \lambda^{(1)}(v)\} \right] \\
\cdot \mathrm{Pr} \left[ \bigcap_{v \in \mathcal{N}_{T_2}(S \cup S')} \{X_v = \lambda^{(1)}(v)\} \right]
$$
$$
\begin{align*}
&= \sum_{\lambda^{(1)}: \mathcal{N}_{T_2}(S \cup S') \to \Sigma^{(1)}} \Pr \left[ \bigcap_{v \in S} \{Y_v = \lambda^{(2)}(v)\} \middle| \bigcap_{v \in \mathcal{N}_{T_2}(S \cup S')} \{X_v = \lambda^{(1)}(v)\} \right] \\
&\quad \cdot \Pr \left[ \bigcap_{v \in S'} \{Y_v = \lambda^{(2)}(v)\} \middle| \bigcap_{v \in \mathcal{N}_{T_2}(S \cup S')} \{X_v = \lambda^{(1)}(v)\} \right] \\
&\quad \cdot \Pr \left[ \bigcap_{v \in \mathcal{N}_{T_2}(S \cup S')} \{X_v = \lambda^{(1)}(v)\} \right] \\
&= \sum_{\lambda^{(1)}: \mathcal{N}_{T_2}(S \cup S') \to \Sigma^{(1)}} \Pr \left[ \bigcap_{v \in S} \{Y_v = \lambda^{(2)}(v)\} \middle| \bigcap_{v \in \mathcal{N}_{T_2}(S)} \{X_v = \lambda^{(1)}(v)\} \right] \\
&\quad \cdot \Pr \left[ \bigcap_{v \in S'} \{Y_v = \lambda^{(2)}(v)\} \middle| \bigcap_{v \in \mathcal{N}_{T_2}(S')} \{X_v = \lambda^{(1)}(v)\} \right] \\
&\quad \cdot \Pr \left[ \bigcap_{v \in \mathcal{N}_{T_2}(S \cup S')} \{X_v = \lambda^{(1)}(v)\} \right].
\end{align*}
$$

Now observe that dist_G(NT_2(S), NT_2(S')) > T_1. Since {X_v}_{v \in V} is a T_1-dependent distribution, it
holds that

$$
\begin{align*}
& \sum_{\lambda^{(1)}: \mathcal{N}_{T_2}(S \cup S') \to \Sigma^{(1)}} \Pr \left[ \bigcap_{v \in S} \{Y_v = \lambda^{(2)}(v)\} \middle| \bigcap_{v \in \mathcal{N}_{T_2}(S)} \{X_v = \lambda^{(1)}(v)\} \right] \\
& \qquad \cdot \Pr \left[ \bigcap_{v \in S'} \{Y_v = \lambda^{(2)}(v)\} \middle| \bigcap_{v \in \mathcal{N}_{T_2}(S')} \{X_v = \lambda^{(1)}(v)\} \right] \\
& \qquad \cdot \Pr \left[ \bigcap_{v \in \mathcal{N}_{T_2}(S \cup S')} \{X_v = \lambda^{(1)}(v)\} \right] \\
&= \sum_{\lambda^{(1)}: \mathcal{N}_{T_2}(S \cup S') \to \Sigma^{(1)}} \Pr \left[ \bigcap_{v \in S} \{Y_v = \lambda^{(2)}(v)\} \middle| \bigcap_{v \in \mathcal{N}_{T_2}(S)} \{X_v = \lambda^{(1)}(v)\} \right] \\
& \qquad \cdot \Pr \left[ \bigcap_{v \in S'} \{Y_v = \lambda^{(2)}(v)\} \middle| \bigcap_{v \in \mathcal{N}_{T_2}(S')} \{X_v = \lambda^{(1)}(v)\} \right] \\
& \qquad \cdot \Pr \left[ \bigcap_{v \in \mathcal{N}_{T_2}(S)} \{X_v = \lambda^{(1)}(v)\} \right] \Pr \left[ \bigcap_{v \in \mathcal{N}_{T_2}(S')} \{X_v = \lambda^{(1)}(v)\} \right] \\
&= \Pr \left[ \bigcap_{v \in S} \{Y_v = \lambda^{(2)}(v)\} \right] \cdot \Pr \left[ \bigcap_{v \in S'} \{Y_v = \lambda^{(2)}(v)\} \right].
\end{align*}
$$

We now prove claim 2. Given any $G, H \in \mathcal{F}$ of size $n_G$ and $n_H$, respectively, consider any subgraph isomorphism $f: \mathcal{N}_{2T_2+T_1(n_G)}(G', G) \to \mathcal{N}_{2T_2+T_1(n_H)}(H', H)$ for any two $G' \subseteq G, H' \subseteq H$ such that $f$ restricted to $G'$ is an isomorphism to $H'$. Let $\{X_v^{(G)}\}_{v \in V(G)}$ and $\{X_v^{(H)}\}_{v \in V(H)}$, and $\{Y_v^{(G)}\}_{v \in V(G)}$ and $\{Y_v^{(H)}\}_{v \in V(H)}$ be the corresponding distributions of interest before and after the combination with the port-numbering algorithm, respectively. Fix any subset of nodes $U \subseteq V(G')$ and consider any family of labels $\{\lambda_u\}_{u \in U}$ indexed by $U$. In order to prove property 1, it is sufficient to show that

$$
\mathrm{Pr} \left[ \bigcap_{u \in U} \{Y_u^{(G)} = \lambda_u\} \right] = \mathrm{Pr} \left[ \bigcap_{u \in U} \{Y_{f(u)}^{(H)} = \lambda_u\} \right].
$$

Notice that $\Pr[\cap_{u \in U} \{Y_u = \lambda_u\}]$ depends solely on the graph $G[\mathcal{N}_{T_2}(U, G)] = \cup_{u \in U} G[\mathcal{N}_{T_2}(u, G)]$, the distribution of the port numbers in $G[\mathcal{N}_{T_2}(U, G)]$, and the random process $\{X_u\}_{u \in \mathcal{N}_{T_2}(U)}$. By hypothesis, $\{X_u^{(G)}\}_{u \in \mathcal{N}_{T_2}(U, G)}$ is equal in law to $\{X_{f(u)}^{(H)}\}_{u \in \mathcal{N}_{T_2}(U, G)}$. Furthermore, the restriction of $f$ to $G[\mathcal{N}_{T_2}(U, G)]$ defines an isomorphism from $G[\mathcal{N}_{T_2}(U, G)]$ to $H[\mathcal{N}_{T_2}(f(U), H)]$, hence the distribution of the port numbers in $G[\mathcal{N}_{T_2}(U, G)]$ is the same as that in $H[\mathcal{N}_{T_2}(f(U), H)]$ because each node permutes the port numbers locally u.a.r. Thus, $\Pr[\cap_{u \in U} \{Y_u^{(G)} = \lambda_u\}]$ must be the same as $\Pr[\cap_{u \in U} \{Y_{f(u)}^{(H)} = \lambda_u\}]$. $\square$
T-dependent distributions over different graphs can be combined to obtain a T-dependent distribution over the graph union.

**Lemma 6.5.** Let {$X_v$}$_{v \in V_1}$ and {$Y_v$}$_{v \in V_2}$ be a T₁-dependent distribution over a graph $G_1 = (V_1, E_1)$ taking values in $\Sigma^{(1)}$, and a T₂-dependent distribution over a graph $G_2 = (V_2, E_2)$ taking values in $\Sigma^{(2)}$, respectively. Assume {$X_v$}$_{v \in V_1}$ and {$Y_v$}$_{v \in V_2}$ to be independent processes. Consider the graph $H = (V = V_1 \cup V_2, E = E_1 \cup E_2)$ and a distribution {$Z_v$}$_{v \in V}$ over H taking values in $\Sigma = (\Sigma^{(1)} \cup \{0\}) \times (\Sigma^{(2)} \cup \{0\})$ defined by

$$Z_v = \begin{cases} (X_v, 0) & \text{if } v \in V_1 \setminus V_2, \\ (X_v, Y_v) & \text{if } v \in V_1 \cap V_2, \\ (0, Y_v) & \text{if } v \in V_2 \setminus V_1. \end{cases}$$

Then, {$Z_v$}$_{v \in V}$ is max($T_1, T_2$)-dependent.

*Proof.* For any vector $\mathbf{v} \in \Sigma_1 \times \cdots \times \Sigma_n$, we write $\mathbf{v}[i]$ to denote its i-th entry. Fix any output labeling $\lambda: V \to \Sigma$ such that $\lambda(v)[2] = 0$ for all $v \in V_1 \setminus V_2$ and $\lambda(v)[1] = 0$ for all $v \in V_2 \setminus V_1$. Observe that for any subset $S \subseteq V$ it holds that

$$\begin{align}
& \mathrm{Pr}[\cap_{v \in S} \{Z_v = \lambda(v)\}] \nonumber \\
& = \mathrm{Pr}[(\cap_{v \in S \cap V_1} \{X_v = \lambda(v)[1]\}) \cap (\cap_{v \in S \cap V_2} \{Y_v = \lambda(v)[2]\})] \nonumber \\
& = \mathrm{Pr}[\cap_{v \in S \cap V_1} \{X_v = \lambda(v)[1]\}] \cdot \mathrm{Pr}[\cap_{v \in S \cap V_2} \{Y_v = \lambda(v)[2]\}], \tag{4}
\end{align}$$

where the latter equality follows by independence between {$X_v$}$_{v \ in V_1}$ and {$Y_v$}$_{v \ in V_2}$. W.l.o.g., suppose $T_1 \ge T_2$. Consider two subsets $S, S' \subseteq V$ such that $\mathrm{dist}_G(S, S') > T_1$. Fix any output labeling $\lambda: V \to \Sigma$ such that $\lambda(v)[2] = 0$ for all $v \in V_1 \setminus V_2$ and $\lambda(v)[1] = 0$ for all $v \in V_2 \setminus V_1$. Using Eq. (4), we have that

$$\begin{align}
& \mathrm{Pr}[\cap_{v \in S \cup S'} \{Z_v = \lambda(v)\}] \nonumber \\
& = \mathrm{Pr}[\cap_{v \in (S \cup S') \cap V_1} \{X_v = \lambda(v)[1]\}] \cdot \mathrm{Pr}[\cap_{v \in (S \cup S') \cap V_2} \{Y_v = \lambda(v)[2]\}] \nonumber \\
& = \mathrm{Pr}[\cap_{v \in (S \cap V_1) \cup (S' \cap V_1)} \{X_v = \lambda(v)[1]\}] \cdot \mathrm{Pr}[\cap_{v \in (S \cap V_2) \cup (S' \cap V_2)} \{Y_v = \lambda(v)[2]\}] \nonumber \\
& = \mathrm{Pr}[\cap_{S \cap V_1} \{X_v = \lambda(v)[1]\}] \cdot \mathrm{Pr}[\cap_{S' \cap V_1} \{X_v = \lambda(v)[1]\}] \tag{5}
\end{align}$$

$$\begin{align}
& \cdot \mathrm{Pr}[\cap_{S \cap V_2} \{Y_v = \lambda(v)[2]\}] \cdot \mathrm{Pr}[\cap_{S' \cap V_2} \{Y_v = \lambda(v)[2]\}] \nonumber \\
& = \mathrm{Pr}[(\cap_{v \in S \cap V_1} \{X_v = \lambda(v)[1]\}) \cap (\cap_{v \in S \cap V_2} \{Y_v = \lambda(v)[2]\})] \tag{6}
\end{align}$$

$$\begin{align}
& \cdot \mathrm{Pr}[(\cap_{v \in S' \cap V_1} \{X_v = \lambda(v)[1]\}) \cap (\cap_{v \in S' \cap V_2} \{Y_v = \lambda(v)[2]\})] \nonumber \\
& = \mathrm{Pr}[\cap_{v \in S} \{Z_v = \lambda(v)\}] \cdot \mathrm{Pr}[\cap_{v \in S'} \{Z_v = \lambda(v)\}], \nonumber
\end{align}$$

where Eq. (5) holds because {$X_v$}$_{v \in V_1}$ is T₁-dependent and {$Y_v$}$_{v \in V_2}$ is T₂-dependent, while Eq. (6) holds because {$X_v$}$_{v \in V_1}$ and {$Y_v$}$_{v \in V_2}$ are independent. $\square$

Now we present a final lemma on the composition of random processes. To do so, we first introduce the notation of random decomposition of a graph.

**Definition 6.6 (Random decomposition).** Let $G = (V, E)$ be any graph and $\mathcal{P}$ a family of subgraphs of $G$. For any $k \in \mathbb{N}$, let $\Gamma(G)$ be a random variable taking values in $\mathcal{P}^k$ that is sampled according to any probability distribution. We say that $\Gamma(G)$ is a random k-decomposition of $G$ in $\mathcal{P}$.
Given a random $k$-decomposition $\Gamma(G)$ of $G$ in $\mathcal{P}$, for any $y \in V \cup E$, we define the random variable $\Gamma(G)_y \in \{0, 1\}^k$ as follows: $\Gamma(G)_y[i] = 1$ if $y$ belongs to $\Gamma(G)[i]$ and 0 otherwise. Notice that $\{\Gamma(G)_y\}_{y \in V \cup E}$ is a random process on $G$. If $\{\Gamma(G)_y\}_{y \in V \cup E}$ is invariant under automorphisms, then we say that the random $k$-decomposition $\Gamma(G)$ is invariant under automorphisms. If, for a family of graphs $\mathcal{F}$ and any graph $G \in \mathcal{F}$, $\{\Gamma(G)_y\}_{y \in V(G) \cup E(G)}$ is $T$-dependent (with $T$ being a function of the size of $G$) and the processes in $\{\{\Gamma(G)_y\}_{y \in V(G) \cup E(G)}: G \in \mathcal{F}\}$ are invariant under subgraph isomorphisms, then we say that the random $k$-decompositions in $\{\Gamma(G): G \in \mathcal{F}\}$ are $T$-dependent and invariant under subgraph isomorphisms.

For a random decomposition, we define the notion of induced random process.

**Definition 6.7 (Induced process).** Let $G = (V, E)$ be a graph that admits a family of subgraphs $\mathcal{P}$. Suppose there exists a random process $\{X_v\}_{v \in V(H(\mathcal{P}))}$ with $H(\mathcal{P})$ being the graph obtained by the disjoint union of all elements of $\mathcal{P}$. Let $\Gamma(G)$ be a random $k$-decomposition of $G$ in $\mathcal{P}$. For all $v \in V$ and $G' \in \mathcal{P}$, define the random process $\{X_v^{(G')}\}_{v \in V}$ by setting $X_v^{(G')} = X_{f_{G'}(v)}$ for all $v \in V(G')$, where $f_{G'}: V(G') \to V(H(\mathcal{P}))$ is the natural immersion of $G'$ into $H(\mathcal{P})$ otherwise set $X_v^{(G')} = 0$. Let $\{Y_v^{(\Gamma(G))}\}_{v \in V}$ be a random process that we define conditional on the output of $\Gamma(G)$: for all $G \in \mathcal{P}^k$, conditional on $\Gamma(G) = G$,

$$Y_v^{(\Gamma(G))} = Y_v^{(G)} = (X_v^{(G[1])}, \dots, X_v^{(G[k])}).$$

The random process $\{Y_v^{(\Gamma(G))}\}_{v \in V}$ on $G$ is said to be induced by the action of $\{X_v\}_{v \in V(H(\mathcal{P}))}$ over the random $k$-decomposition $\Gamma(G)$.

Now we present a result on the induced random process whenever the random decomposition and the family of random processes that acts on the random decomposition meet some invariance properties.

**Lemma 6.8.** Let $\mathcal{F}$ be a family of graphs. For any $G = (V, E) \in \mathcal{F}$, let $\mathcal{P}_G$ be any family of subgraphs of $G$ that is closed under node removal and disjoint graph union, that is, if $G_1, G_2 \in \mathcal{P}_G$ and $V(G_1) \cap V(G_2) = \emptyset$, then $G_1 \cup G_2 \in \mathcal{P}_G$. Furthermore, suppose that, for each pair of isomorphic subgraphs $G_1, G_2 \subseteq G$, $G_1 \in \mathcal{P}_G \implies G_2 \in \mathcal{P}_G$. Moreover, let $\Gamma(G)$ be a random $k$-decomposition of $G$ in $\mathcal{P}_G$ that is $T_1$-dependent, and suppose that the random decompositions in $\{\Gamma(G): G \in \mathcal{F}\}$ are invariant under subgraph isomorphism. Suppose there is $T_2$-dependent distribution $\{X_v\}_{v \in V(H(\mathcal{P}_G))}$, taking values in a finite set $\Sigma$, such that $\{\{X_v\}_{v \in V(H(\mathcal{P}_G))}: G \in \mathcal{F}\}$ is invariant under subgraph isomorphism, where $H(\mathcal{P}_G)$ is obtained by the disjoint union of a copy of each element of $\mathcal{P}_G$. Let $\{Y_v^{(\Gamma(G))}\}_{v \in V(G)}$ be the random process induced by the action of $\{X_v\}_{v \in V(H(\mathcal{P}_G))}$ over $\Gamma(G)$. Then, $\{Y_v^{(\Gamma(G))}\}_{v \in V(G)}$ is a $(T_1 + 2T_2)$-dependent distribution. Furthermore, the processes in $\{\{X_v\}_{v \in V(H(\mathcal{P}_G))}: G \in \mathcal{F}\}$ are invariant under subgraph isomorphism.

**Proof.** Fix $G \in \mathcal{F}$ and let $\Gamma = \Gamma(G)$, $\mathcal{P} = \mathcal{P}_G$. Since $\mathcal{P}^k$ might be uncountable, we consider the density function $f_\Gamma$ and the probability measure $\mathbb{P}$ associated to $\Gamma$. Consider two subsets of nodes $S, S' \subseteq V$ at distance at least $\max(T_1, T_2) + 1$. Fix any labeling $\lambda: V \to \Sigma^k$. It holds that

$$ \begin{align} & \mathrm{Pr} \left[ \bigcap_{v \in S \cup S'} \{Y_v^{(\Gamma)} = \lambda(v)\} \right] \nonumber \\ &= \int_{\mathcal{P}^k} \mathrm{Pr} \left[ \bigcap_{v \in S \cup S'} \{Y_v^{(\Gamma)} = \lambda(v)\} \mid \Gamma = G \right] f_\Gamma(G) \, d\mathbb{P} \tag{7} \\ &= \int_{\mathcal{P}^k} \mathrm{Pr} \left[ \bigcap_{v \in S \cup S'} \{Y_v^{(G)} = \lambda(v)\} \right] f_\Gamma(G) \, d\mathbb{P} \nonumber \end{align} $$
$$ = \int_{\mathcal{P}^k} \Pr[\cap_{v \in S} \{Y_v^{\mathbf{G}} = \lambda(v)\}] \Pr[\cap_{v \in S'} \{Y^{\mathbf{G}} = \lambda(v)\}] f_{\Gamma}(\mathbf{G}) \, d\mathbb{P} \quad (8) $$

$$ = \int_{\mathcal{P}^k} \prod_{i \in [k]} \Pr[\cap_{v \in S} \{X_v^{\mathbf{G}[i]} = \lambda(v)[i]\}] \Pr[\cap_{v \in S'} \{X_v^{\mathbf{G}[i]} = \lambda(v)[i]\}] f_{\Gamma}(\mathbf{G}) \, d\mathbb{P}, \quad (9) $$

where Eq. (7) holds by the law of total probability, Eq. (8) holds since $\{Y_v^{(\mathbf{G})}\}_{v \in V}$ is $T_2$-dependent for all $\mathbf{G} \in \mathcal{P}^k$ by Lemma 6.5, and Eq. (9) holds since $\{X_v^{\mathbf{G}[i]}\}_{v \in V}$ and $\{X_v^{\mathbf{G}[j]}\}_{v \in V}$ are independent if $i \neq j$. Notice that, for any set $S \subseteq V$, $G' = G[i][\mathcal{N}_{T_2}(S, G[i])] \in \mathcal{P}$ and the event $\cap_{v \in S} \{X_v^{\mathbf{G}[i]} = \lambda(v)[i]\}$ has the same probability as $\cap_{v \in S} \{X_v^{G'} = \lambda(v)[i]\}$ because $\{X_v\}_{v \in V(H(\mathcal{P}))}$ is invariant under subgraph isomorphisms.

For any subset $U \subseteq V$ and any integer $T \ge 0$, let

$$ \mathcal{H}(T, U) = \left\{ (\mathbf{G}[1][\mathcal{N}_T(U, \mathbf{G}[1])], \dots, \mathbf{G}[k][\mathcal{N}_T(U, \mathbf{G}[k])]) \mid \mathbf{G} \in \mathcal{P}^k \right\} \subseteq \mathcal{P}^k, $$

and let $\mathbb{P}[\mathcal{H}(T, U)]$ be the restriction of $\mathbb{P}$ to $\mathcal{H}(T, U)$ defined as follows: for any event $E$,

$$ \mathbb{P}[\mathcal{H}(T, U)](E) = \mathbb{P}(E \cap \mathcal{H}(T, U)) / \mathbb{P}(\mathcal{H}(T, U)). $$

Finally, define the random variable $\Gamma^{(T,U)}$ to be a $k$-dimensional vector, taking values in $\mathcal{H}(T, U)$, whose $i$-th entry is $\Gamma[i][\mathcal{N}_T(U, \Gamma[i])]$, and let $f_{\Gamma^{(T,U)}}$ be its density function. Define $U = S \cup S'$: Eq. (9) becomes

$$ \int_{\mathcal{P}^k} \prod_{i \in [k]} \Pr[\cap_{v \in S} \{X_v^{\mathbf{G}[i]} = \lambda(v)[i]\}] \Pr[\cap_{v \in S'} \{X_v^{\mathbf{G}[i]} = \lambda(v)[i]\}] f_{\Gamma}(\mathbf{G}) \, d\mathbb{P} \quad (10) \\ = \int_{\mathcal{H}(T_2, U)} \prod_{i \in [k]} \Pr[\cap_{v \in S} \{X_v^{\mathbf{H}[i]} = \lambda(v)[i]\}] \Pr[\cap_{v \in S'} \{X_v^{\mathbf{H}[i]} = \lambda(v)[i]\}] f_{\Gamma^{(T_2, U)}}(\mathbf{H}) \, d\mathbb{P}[\mathcal{H}(T_2, U)]. $$

Now notice that, since the random decomposition $\Gamma$ is $T_1$-dependent and $\mathrm{dist}_G(S, S') > T_1 + 2T_2$, the probability space $\mathcal{H}(T_2, U)$ (with measure $\mathbb{P}[\mathcal{H}(T_2, U)])$ is isomorphic to the product space $\mathcal{H}(T_2, S) \times \mathcal{H}(T_2, S')$ (with product measure $\mathbb{P}[\mathcal{H}(T_2, S)] \times \mathbb{P}[\mathcal{H}(T_2, S')])$. The isomorphism brings any element

$$ (\mathbf{G}[1][\mathcal{N}_{T_2}(U, \mathbf{G}[1])], \dots, \mathbf{G}[k][\mathcal{N}_{T_2}(U, \mathbf{G}[k])]) $$

of $\mathcal{H}(T_2, U)$ into

$$ ((\mathbf{G}[1][\mathcal{N}_{T_2}(S, \mathbf{G}[1])], \dots, \mathbf{G}[k][\mathcal{N}_{T_2}(S, \mathbf{G}[k])]), (\mathbf{G}[1][\mathcal{N}_{T_2}(S', \mathbf{G}[1])], \dots, \mathbf{G}[k][\mathcal{N}_{T_2}(S', \mathbf{G}[k])])) $$

which belongs to $\mathcal{H}(T_2, S) \times \mathcal{H}(T_2, S')$. Hence, we get

$$ \int_{\mathcal{H}(T_2, U)} \prod_{i \in [k]} \Pr[\cap_{v \in S} \{X_v^{\mathbf{H}[i]} = \lambda(v)[i]\}] \Pr[\cap_{v \in S'} \{X_v^{\mathbf{H}[i]} = \lambda(v)[i]\}] f_{\Gamma^{(T_2, U)}}(\mathbf{H}) \, d\mathbb{P}[\mathcal{H}(T_2, S)] \\ = \int_{\mathcal{H}(T_2, S)} \int_{\mathcal{H}(T_2, S')} \prod_{i \in [k]} \Pr[\cap_{v \in S} \{X_v^{\mathbf{H}[i]} = \lambda(v)[i]\}] \Pr[\cap_{v \in S'} \{X_v^{\mathbf{H}[i]} = \lambda(v)[i]\}] \\ \cdot f_{\Gamma^{(T_2, S)}}(\mathbf{H}_1) f_{\Gamma^{(T_2, S')}}(\mathbf{H}_2) \, d\mathbb{P}[\mathcal{H}(T_2, S)] \, d\mathbb{P}[\mathcal{H}(T_2, S')]. $$

The latter becomes

$$ \int_{\mathcal{H}(T_2, S)} \int_{\mathcal{H}(T_2, S')} \prod_{i \in [k]} \Pr[\cap_{v \in S} \{X_v^{\mathbf{H}[i]} = \lambda(v)[i]\}] \Pr[\cap_{v \in S'} \{X_v^{\mathbf{H}[i]} = \lambda(v)[i]\}] $$
$$
\begin{align}
& \cdot f_{\Gamma(T_2, S)}(\mathbf{H}_1) f_{\Gamma(T_2, S')}(\mathbf{H}_2) \mathrm{d}\mathbb{P}[\mathcal{H}(T_2, S)] \mathrm{d}\mathbb{P}[\mathcal{H}(T_2, S')] \nonumber \\
&= \int_{\mathcal{H}(T_2, S)} \prod_{i \in [k]} \mathrm{Pr} \left[ \cap_{v \in S} \{ X_v^{\mathbf{H}[i]} = \lambda(v)[i] \} \right] f_{\Gamma(T_2, S)}(\mathbf{H}_1) \mathrm{d}\mathbb{P}[\mathcal{H}(T_2, S)] \nonumber \\
& \cdot \int_{\mathcal{H}(T_2, S')} \prod_{i \in [k]} \mathrm{Pr} \left[ \cap_{v \in S'} \{ X_v^{\mathbf{H}[i]} = \lambda(v)[i] \} \right] f_{\Gamma(T_2, S')}(\mathbf{H}_2) \mathrm{d}\mathbb{P}[\mathcal{H}(T_2, S')] \nonumber \\
&= \int_{\mathcal{P}^k} \prod_{i \in [k]} \mathrm{Pr} \left[ \cap_{v \in S} \{ X_v^{\mathbf{G}[i]} = \lambda(v)[i] \} \right] f_{\Gamma(\mathbf{G})} \mathrm{d}\mathbb{P} \tag{11} \\
& \cdot \int_{\mathcal{P}^k} \prod_{i \in [k]} \mathrm{Pr} \left[ \cap_{v \in S'} \{ X_v^{\mathbf{G}[i]} = \lambda(v)[i] \} \right] f_{\Gamma(\mathbf{G})} \mathrm{d}\mathbb{P} \nonumber \\
&= \mathrm{Pr} \left[ \cap_{v \in S} \{ Y_v^{(\Gamma(G))} = \lambda(v) \} \right] \mathrm{Pr} \left[ \cap_{v \in S'} \{ Y_v^{(\Gamma(G))} = \lambda(v) \} \right], \nonumber
\end{align}
$$

where Eq. (11) follows by the same reasoning as for Eq. (10) but in reverse.

Now we want to prove that $\{Y_v^{(\Gamma(G))}\}_{v \in V} : G \in \mathcal{F}$ is invariant under subgraph isomorphism. Fix any two graphs $G, H \in \mathcal{F}$ of sizes $n_G$ and $n_H$, respectively. Consider any isomorphism $\alpha$ between the radius-$(T_1(n_G) + 2T_2(n_G))$ neighborhoods of any subgraph $G' \subseteq G$ and the radius-$(T_1(n_H) + 2T_2(n_H))$ neighborhoods of any subgraph $H' \subseteq H$, such that the restriction of $\alpha$ to $G'$ is an isomorphism to $H'$. With an abuse of notation, for any subgraph $K \subseteq G'$, let us denote $\alpha(K) \subseteq H'$ its isomorphic image in $H'$ through $\alpha$. Let $T_G = T_1(n_G) + 2T_2(n_G)$ and $T_H = T_1(n_H) + 2T_2(n_H)$. Fix any labeling $\lambda : V \to \Sigma^k$. We have that

$$
\begin{align*}
& \mathrm{Pr} \left[ \cap_{v \in V(G')} \{ Y_v^{(\Gamma(G))} = \lambda(v) \} \right] \\
&= \int_{\mathcal{P}_G^k} \mathrm{Pr} \left[ \cap_{v \in V(G')} \{ Y_v^{(\Gamma(G))} = \lambda(v) \} \mid \Gamma(G) = \mathbf{G} \right] f_{\Gamma(G)}(\mathbf{G}) \mathrm{d}\mathbb{P}_G. \\
&= \int_{\mathcal{P}_G^k} \mathrm{Pr} \left[ \cap_{v \in V(G')} \{ Y_v^{(\mathbf{G})} = \lambda(v) \} \right] f_{\Gamma(G)}(\mathbf{G}) \mathrm{d}\mathbb{P}_G \\
&= \int_{\mathcal{P}_G^k} \prod_{i \in [k]} \mathrm{Pr} \left[ \cap_{v \in V(G')} \{ X_v^{(\mathbf{G}[i])} = \lambda(v)[i] \} \right] f_{\Gamma(G)}(\mathbf{G}) \mathrm{d}\mathbb{P}_G \\
&= \int_{\mathcal{H}_G(T_G, V(G'))} \prod_{i \in [k]} \mathrm{Pr} \left[ \cap_{v \in V(G')} \{ X_v^{(\mathbf{H}[i])} = \lambda(v)[i] \} \right] f_{\Gamma(G)(T_G, V(G'))}(\mathbf{H}) \mathrm{d}\mathbb{P}_G(\mathcal{H}_G(T_G, V(G'))). \\
&= \int_{\mathcal{H}_G(T_G, V(G'))} \prod_{i \in [k]} \mathrm{Pr} \left[ \cap_{v \in V(G')} \{ X_{\alpha(v)}^{(\alpha(\mathbf{H}[i]))} = \lambda(v)[i] \} \right] f_{\Gamma(G)(T_G, V(G'))}(\mathbf{H}) \mathrm{d}\mathbb{P}_G(\mathcal{H}_G(T_G, V(G'))),
\end{align*}
$$

where the latter holds because

$$
\mathrm{Pr} \left[ \cap_{v \in V(G')} \{ X_v^{(\mathbf{H}[i])} = \lambda(v)[i] \} \right] = \mathrm{Pr} \left[ \cap_{v \in V(G')} \{ X_{\alpha(v)}^{(\alpha(\mathbf{H}[i]))} = \lambda(v)[i] \} \right]
$$

as $\{\{X_v\}_{v \in V(H(\mathcal{P}_G))} : G \in \mathcal{F}\}$ is $T_2$-dependent and invariant under subgraph isomorphism. Furthermore, since the processes in $\{\Gamma(G) : G \in \mathcal{F}\}$ are $T_1$-dependent and invariant under subgraph isomorphism, we have that $f_{\Gamma(G)(T_G, V(G'))}(\mathbf{H}) = f_{\Gamma(H)(T_H, V(H'))}((\alpha(\mathbf{H}[1]), \dots, \alpha(\mathbf{H}[k])))$ almost everywhere in $\mathcal{H}_G(T_G, V(G'))$, and that the probability space $\mathcal{H}_G(T_G, V(G'))$ with measure $\mathrm{d}\mathbb{P}_G(\mathcal{H}_G(T_G, V(G')))$ is isomorphic to $\mathcal{H}_H(T_H, V(H'))$ with measure $\mathrm{d}\mathbb{P}_H(\mathcal{H}_H(T_H, V(H')))$, where the isomorphism brings
H into $(\alpha(\mathbf{H}[1]), \dots, \alpha(\mathbf{H}[k]))$. Hence,

$$
\begin{align*}
& \int_{\mathcal{H}_G(T_G, V(G'))} \prod_{i \in [k]} \Pr[\cap_{v \in V(G')} \{X_{\alpha(v)}^{(\alpha(\mathbf{H}[i]))} = \lambda(v)[i]\}] f_{\Gamma(G)(T_G, V(G'))}(\mathbf{H}) \, d\mathbb{P}_G(\mathcal{H}_G(T_G, V(G')) \\
&= \int_{\mathcal{H}_H(T_H, V(H'))} \prod_{i \in [k]} \Pr[\cap_{v \in V(H')} \{X_v^{(\mathbf{H}[i]))} = \lambda(v)[i]\}] f_{\Gamma(H)(T_H, V(H'))}(\mathbf{H}) \, d\mathbb{P}_H(\mathcal{H}_H(T_H, V(H')) \\
&= \Pr[\cap_{v \in V(H')} \{Y_v^{(\Gamma(H))} = \lambda(v)\}],
\end{align*}
$$

concluding the proof.

<figure><img src="image_2.png" /></figure>

**Remark 6.9.** When the underlying graph is a directed graph, Lemma 6.8 guarantees invariance under subgraph isomorphisms that keep edge orientation.

We are going to work on rooted pseudotrees and pseudoforests. A *pseudotree* is a graph that is connected and contains at most one cycle. A *pseudoforest* is a graph obtained by the disjoint union of pseudotrees; an equivalent definition of pseudoforest is a graph in which each connected component has no more edges than vertices. Note that a pseudotree might contain multiple edges: however, we assume it does not contain self-loops as self-loops are useless communication links in the LOCAL model. A *rooted tree* is a tree where each edge is oriented and all nodes have outdegree at most 1: it follows that all but one node have outdegree exactly 1 and one node (the *root*) has outdegree 0. Trivially, a tree can be rooted by selecting one node and orienting all edges towards it. A *rooted pseudotree* is a pseudotree where each edge is oriented and each node has outdegree at most 1: if the pseudotree contains a cycle, then all nodes necessarily have outdegree exactly 1. Any pseudotree can be oriented so that it becomes rooted: just orient the cycle first (if it exists) in a consistent way, then remove it, and make the remaining trees rooted at nodes that belonged to the cycle. A *rooted pseudoforest* is the union of rooted pseudotrees.

We will show that pseudoforests of maximum degree $\Delta$ admit a $O(\log^* \Delta)$-dependent 3-coloring distributions. In order to do so, we use a color reduction technique that follows by known revisions of the Cole-Vishkin technique [29, 42].

**Lemma 6.10** (port-numbering algorithm for color reduction in pseudoforests [29, 42]). Let $G$ be a pseudoforest with countably many nodes. Assume $G$ is given as an input a $k$-coloring for some $k \ge 3$. There exists a deterministic port-numbering algorithm that does not depend on the size of $G$ and outputs a $3$-coloring of $G$ in time $O(\log^* k)$.

Now we are ready to prove our result on pseudoforests.

**Lemma 6.11** (Finitely-dependent coloring of rooted pseudoforests). Let $\mathcal{F}$ be a family of rooted pseudoforests of countably many nodes of maximum degree $\Delta$. Then, there exists an outcome that associates to each graph $G \in \mathcal{F}$ a $O(\log^* \Delta)$-dependent distribution on the vertices of $G$ that gives a $3$-coloring of $G$. Furthermore, the family of distributions outputted by the outcome are invariant under subgraph isomorphisms.

*Proof.* Let us fix the rooted pseudoforest $G \in \mathcal{F}$. Let $\mathcal{P}_G$ be the family of all subgraphs of $G$ formed by the disjoint union of directed paths and cycles. Notice that $\mathcal{P}_G$ is closed under node removal and disjoint graph union. Furthermore, for any two pair of isomorphic subgraphs $G_1, G_2 \subseteq G$, $G_1 \in \mathcal{P}_G \implies G_2 \in \mathcal{P}_G$. Let $H(\mathcal{P}_G)$ be the graph formed by the disjoint union of a copy of each element of $\mathcal{P}_G$. By Corollary 6.3, $H(\mathcal{P}_G)$ admits a 1-dependent 4-coloring distribution $\{X_v\}_{v \in H(\mathcal{P}_G)}$ (with colors in [4]), such that $\{\{X_v\}_{v \in H(\mathcal{P}_G)} : G \in \mathcal{F}\}$ is invariant under subgraph isomorphism.
<figure><img src="image_3.png" /><figcaption>Figure 1: A decomposition of rooted pseudoforests in directed paths and cycles: each node $v$ colors its indegree neighbors with a uniformly sampled permutation of the elements in $[\text{indeg}(v)]$. The graph induced by nodes colored with color $i$ is a disjoint union of directed paths and cycles.</figcaption></figure>

Consider now a (non-proper) coloring of the pseudoforest in which each node $u$ colors its indegree neighbors with a permutation of $\{1, \dots, \text{indeg}(u)\}$ sampled uniformly at random: if a node has outdegree zero, then it is deterministically colored with color 1. Such a coloring is described by a 2-dependent distribution $\{Z_v\}_{v \in V}$ that is (trivially) invariant under subgraph isomorphisms that keep edge orientation. Also, $\{Z_v\}_{v \in V}$ identifies $\Delta_{\text{in}}$ disjoint random subset of nodes $V_1, \dots, V_{\Delta_{\text{in}}}$, where nodes in $V_i$ are colored with the color $i$, and $\Delta_{\text{in}}$ is the maximum indegree of the graph. Let $\Gamma(G) = (G[V_1], \dots, G[V_{\Delta_{\text{in}}}$]), where $\Gamma(G)[i]$ is the random graph induced by $V_i$. Furthermore, observe that, the output of $\Gamma(G)[i]$ is the disjoint union of oriented paths and/or oriented cycles, with $\Gamma(G)[i]$ being the $i$-th entry of the $\Delta_{\text{in}}$-tuple $\Gamma(G)$ (see Fig. 1). Notice that process $\Gamma(G)$ is 2-dependent and is a random $\Delta_{\text{in}}$-decomposition of $G$ in $\mathcal{P}_G$ (according to Definition 6.6), such that the random decompositions in $\{\Gamma(G) : G \in \mathcal{F}\}$ are invariant under subgraph isomorphism. By Lemma 6.8, the random process $\{Y_v^{(\Gamma(G))}\}_{v \in V}$, that is induced by the action of $\{X_v\}_{v \in H(\mathcal{P}_G)}$ over the random $\Delta_{\text{in}}$-decomposition $\Gamma(G)$ (according to Definition 6.7), is a 4-dependent distribution that gives a $4\Delta_{\text{in}}$-coloring of $G$: in fact, $\Gamma(G)[i]$ and $\Gamma(G)[j]$ are disjoint if $i \neq j$, hence only one entry of $Y_v^{(\Gamma(G))}$ is non-zero, for all $v \in V$.

We then combine $\{Y_v^{(\Gamma(G))}\}_{v \in V}$ and a modified version of the port-numbering algorithm from Lemma 6.10 where at round 0 each node permutes port numbers locally u.a.r.: by Lemma 6.4, we obtain an $O(\log^* \Delta)$-dependent 3-coloring distribution $\{Q_v^{(G)}\}_{v \in V(G)}$ of $G$ such that processes in $\{{Q_v^{(G)}}\}_{v \in V(G)} : G \in \mathcal{F}\}$ are invariant under subgraph isomorphisms. $\square$

Our finitely-dependent coloring of pseudoforests can be used as a baseline to provide a $(\Delta + 1)$-coloring of graphs with maximum degree $\Delta$. The tool we use is again an application of the Cole-Vishkin color reduction technique [56].

**Lemma 6.12** (port-numbering algorithm for color reduction of general graphs [56]). Let $G = (V, E)$ be a graph with maximum degree $\Delta$ and countably many nodes. Suppose $G$ is given in input a $k$-coloring
<figure><img src="image_4.png" /><figcaption>(a) Each node $v$ rearranges its port numbers uniformly at random.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(b) The $\Delta = 5$ rooted pseudoforests that we take by considering port numbers $i \in [\Delta]$.</figcaption></figure>

<caption>Figure 2: A decomposition of a graph of maximum degree $\Delta = 5$ in rooted pseudoforests: for the sake of image clarity, we focus on the undirected case. In Fig. 2a, each node $v$ rearranges its port-numbers with a uniformly sampled permutation of the elements in $[\deg(v)]$. As shown in Fig. 2b, edges hosting port number $i$ at some endpoint are oriented away from that port (in case both endpoints host port number $i$, the edge is duplicated) and form a rooted pseudoforest.</caption>
for some $k \ge \Delta + 1$. There exists a deterministic port-numbering algorithm that does not depend on
the size of the input graph and outputs a $(\Delta + 1)$-coloring of $G$ in time $O(\log^* k + \sqrt{\Delta \log \Delta})$.

We first present a corollary of Lemma 6.12 where we characterize the combination of an input
finitely-dependent coloring distribution and the port-numbering color-reduction algorithm.

**Corollary 6.13.** Let $G = (V, E)$ be a graph with maximum degree $\Delta$ and countably many nodes. Let $\{X_v\}_{v \in V}$ be a $T$-dependent distribution that gives a $k$-coloring of $G$, with $k \ge \Delta+1$. Then there exists a distribution $Y_{vv \in V}$ that gives a $(\Delta+1)$-coloring of $G$ and is $O(\log^* k + \sqrt{\Delta \log \Delta} + T)$-dependent. Furthermore, if $\{X_v\}_{v \in V}$ is invariant under subgraph isomorphism, then so it is $\{Y_v\}_{v \in V}$.

*Proof.* We combine the distribution $\{X_v\}_{v \in V}$ with a modified version of the port-numbering algorithm from Lemma 6.12 where at round 0 each node permutes port numbers locally u.a.r.: Lemma 6.4 implies the existence of an $O(\log^* k + \sqrt{\Delta \log \Delta} + T)$-dependent ($\Delta+1$)-coloring distribution of $G$. If $\{X_v\}_{v \in V}$ is invariant under subgraph isomorphism, Lemma 6.4 implies that $\{Y_v\}_{v \in V}$ has the same property. $\square$

**Lemma 6.14 (Finitely-dependent coloring of bounded-degree graphs).** Let $\mathcal{F}$ be a family of graphs of countably many nodes and maximum degree $\Delta$. Then, there exists an outcome that associates to each graph $G \in \mathcal{F}$ an $O(\sqrt{\Delta \log \Delta})$-dependent distribution on the vertices of $G$ that gives a $(\Delta+1)$-coloring of $G$. Furthermore, the family of distributions outputted by the outcome are invariant under subgraph isomorphisms.

*Proof.* Let us fix $G = (V, E) \in \mathcal{F}$ First, if $G$ is not directed, then duplicate each edge and give to each pair of duplicates different orientations. Since a coloring of the original graph is a proper coloring if and only if the same coloring is proper in the directed version, w.l.o.g., we can assume $G$ to be directed.

Let $\mathcal{P}_G$ be a family of all subgraphs of $G$ formed by rooted pseudotrees and disjoint union of rooted pseudotrees. Notice that $\mathcal{P}_G$ is closed under node removal and disjoint graph union. Furthermore, for any two pair of isomorphic subgraphs $G_1, G_2 \subseteq G$, $G_1 \in \mathcal{P}_G \implies G_2 \in \mathcal{P}_G$. The graph $H(\mathcal{P}_G)$ that is the disjoint union of all elements of copies of each $\mathcal{P}_G$ is a rooted pseudoforest of maximum degree $\Delta$ and, by Lemma 6.11, admits a 3-coloring $O(\log^* \Delta)$-dependent distribution $\{X_v\}_{v \in H(\mathcal{P}_G)}$ such that processes in $\{\{X_v\}_{v \in H(\mathcal{P}_G)} : G \in \mathcal{F}\}$ are invariant under subgraph isomorphism.

Now, consider a process in which each node $v$ samples uniformly at random a permutation of
a port numbering from $\{1, \dots, \text{outdeg}(v)\}$ for its outgoing edges. For each $i \in [\Delta_{\text{out}}]$, consider the
graph $G_i$ induced by edges that host port $i$: notice that $G_i$ is a rooted pseudoforest as each node
has at most one out-edge with port $i$. If a node has degree 0, it deterministically joins $G_1$, which
remains a pseudoforest. The random choice of port numbering defines a random variable $\Gamma \in \mathcal{P}_G^k$,
where $\Gamma[i]$ is the graph induced by port number $i$: according to Definition 6.6, we obtain a random
$\Delta_{\text{out}}$-decomposition $\Gamma(G)$ of $G$ in $\mathcal{P}_G$ which is 2-dependent (by construction): also, the random
decompositions in $\{\Gamma(G) : G \in \mathcal{F}\}$ are invariant under subgraph isomorphisms. For an example of a
possible output of the random decomposition, see Fig. 2.

Hence, the random process $\{Y_v^{(\Gamma(G))}\}_{v \in V}$ from Definition 6.7 is well defined, and provides a
proper $3^\Delta$-coloring of $G$. By Lemma 6.8, the random process $\{Y_v^{(\Gamma(G))}\}_{v \in V}$ is $O(\log^* \Delta)$-dependent
and, when $G \in \mathcal{F}$ varies, the processes $\{Y_v^{(\Gamma(G))}\}_{v \in V}$ are invariant under subgraph isomorphisms.

By Corollary 6.13 we obtain an $O(\sqrt{\Delta \log \Delta})$-dependent ($\Delta+1$)-coloring distribution on $G$ that
is invariant under subgraph isomorphism (as $G \in \mathcal{F}$ varies). $\square$

Lemma 6.14 answers an open question posed by Holroyd [44]. (See also Corollary 1.3 and the
discussion around it.)
**Corollary 6.15.** Let $G = (V, E)$ be the infinite $d$-regular tree. There exists a finitely-dependent distribution giving a $(d+1)$-coloring of $G$ that is invariant under automorphisms.

*Proof.* Finding a $(d+1)$-coloring of any $d$-regular tree has complexity $O(1)$ in SLOCAL; the coloring can just be performed greedily. Lemma 6.14 yields the desired result. □

Consider any graph $G = (V, E)$. For any $k \in \mathbb{N}_+$, a distance-$k$ coloring of $G$ is an assignment of colors $c: V \to \Sigma$ such that, for each node $v \in V$, all nodes in $\mathcal{N}_k(v) \setminus \{v\} = \{u \in V: \text{dist}_G(u, v) \le k\} \setminus \{v\}$ have colors that are different from $c(v)$.

It is well known that any LCL problem $\Pi$ that has complexity $O(\log^* n)$ in the LOCAL model has the following property: there exists a constant $k \in \mathbb{N}_+$ (that depends only on the hidden constant in $O(\log^* n)$) such that, if the input graph is given a distance-$k$ coloring, then $\Pi$ is solvable in time $O(1)$ in the port-numbering model [20]. Furthermore, no knowledge of the size of the input graph is required.

**Theorem 6.16.** Consider any LCL problem $\Pi$ with checking radius $r$ that has complexity $T \ge r$ in the LOCAL model over a family $\mathcal{F}$ of graphs with maximum degree $\Delta$, where $T = O(\log^* n)$ for input graphs of size $n$. For each $G \in \mathcal{F}$, there exists an $O(f(\Delta))$-dependent distribution $\{Y_v^{(G)}\}_{v \in V(G)}$ that solves $\Pi$ over $G$. Furthermore, the processes in $\{\{Y_v^{(G)}\}_{v \in V(G)}: G \in \mathcal{F}\}$ are invariant under subgraph isomorphisms.

*Proof.* Fix $G \in \mathcal{F}$ of size $n$. As said before, there exists a constant $k \in \mathbb{N}_+$ (that depends only on the description of the $\Pi$) such that, if the input graph is given a distance-$k$ coloring, then $\Pi$ is solvable in time $O(1)$ (hiding some dependence on $\Delta$) in the port-numbering model [20]. Furthermore, no knowledge of the size of the input graph is required. Consider the power graph $G^k$, where $k \ge T$, defined by $G^k = \{V, E^k\}$ with $E^k = \{{\{u, v\}: u, v \in V, \text{dist}_G(u, v) \le k\}}$. The maximum degree of $G^k$ is $\Delta^k$. By Lemma 6.14, $G^k$ admits an $O(\sqrt{k\Delta^k \log \Delta})$-dependent $(\Delta^k + 1)$-coloring distribution $\{X_v\}_{v \in V}$ that is invariant under subgraph isomorphisms (as $G \in \mathcal{F}$ varies). Notice that such a coloring provides a distance-$k$ coloring for $G$.

Let $\mathcal{A}$ be the algorithm in port-numbering model that solves $\Pi$ in time $O(1)$ while given the distance-$k$ coloring in input. Consider a port-numbering algorithm $\mathcal{A}'$ that simulates $\mathcal{A}$ and is defined as follows: At round 0, $\mathcal{A}'$ permutes ports locally u.a.r. Then, $\mathcal{A}'$ simply simulates $\mathcal{A}$ using identifiers given by the distance-$k$ coloring and properly solves $\Pi$ by the hypotheses. Notice that $\{Y_v\}_{v \in V}$, that is, the random process induced by combining $\{X_v\}_{v \in V}$ and $\mathcal{A}'$ is a $O(f(\Delta))$-dependent distribution on $G$ by Lemma 6.4 with the required invariance properties, and we get the thesis by choosing $k = T$. □

# 7 Simulation of online-LOCAL in SLOCAL for rooted trees

In this section, we show how to turn an online-LOCAL algorithm solving an LCL problem in rooted forests into a deterministic SLOCAL algorithm solving the same problem. More concretely, we prove the following theorems:

**Theorem 7.1.** Let $\Pi$ be an LCL problem with degree constraint $\Delta$, input label set $\Sigma_{in}$, output label set $\Sigma_{out}$, and checking radius $r > 0$. In addition, let $\mathcal{A}$ be an online-LOCAL algorithm solving $\Pi$ with locality $T(n)$ over rooted forests. Then the following holds:

1. If $\mathcal{A}$ is deterministic, then there exists a deterministic SLOCAL algorithm solving $\Pi$ with locality $O(r) + T(2^{O(n^3)})$.
2. If A is randomized and has success probability $p(n) > 0$, then there exists a deterministic SLOCAL algorithm solving $\Pi$ with locality $O(r) + T(2^{O(n^3)} + 2^{O(2^{n^2})} \cdot \log \frac{1}{p(n)})$.

Theorem 7.1 implies that any randomized online-LOCAL algorithm with locality $o(\log \log \log n)$ solving an LCL $\Pi$ over rooted trees can be turned into an SLOCAL algorithm solving $\Pi$ with locality $o(\log n)$. Next theorem shows that, over rooted trees, the class of LCL problems with complexity $o(\log n)$ is the same as that of LCL problems with complexity $O(1)$.

**Theorem 7.2.** Let A be an SLOCAL algorithm solving an LCL problem $\Pi$ that runs with locality $o(\log_\Delta n)$ over rooted forests of maximum degree $\Delta$ and $n$ nodes. Then, there exists an SLOCAL algorithm B solving $\Pi$ with locality $O(1)$.

It is folklore that any $O(1)$-round SLOCAL algorithm solving an LCL can be turned into an $O(\log^* n)$-round LOCAL algorithm solving the same LCL, implying the thesis of Theorem 1.5.

## 7.1 Amnesiac online-LOCAL algorithms

We start by formalizing what an online-LOCAL algorithm sees when run for a fixed number of steps on a graph. We then define formally what we mean by amnesiac algorithms:

**Definition 7.3 (Partial online-LOCAL run of length $\ell$).** Let $G$ be a graph with an ordering of nodes $v_1, v_2, \dots, v_n$. Consider the subgraph $G_\ell \subseteq G$ induced by the radius-$T$ neighborhoods of the first $\ell$ nodes $v_1, \dots, v_\ell$. We call $(G_\ell, (v_1, \dots, v_\ell))$ the partial online-LOCAL run of length $\ell$ of $G$ as this is exactly the information that an online-LOCAL algorithm would know about $G$ when deciding the output for node $v_\ell$.

We denote by the pair $(\bar{G}_\ell, (w_1, \dots, w_k))$ where $\bar{G}_\ell \subseteq G_\ell$ is the connected component containing $v_\ell$, and $(w_1, \dots, w_k)$ is the maximal subsequence of $(v_1, \dots, v_\ell)$ of nodes that belong to $\bar{G}_\ell$. In such case, $k$ is the length of $(G_\ell, (v_1, \dots, v_\ell))[v_\ell]$. Trivially, $w_k = v_\ell$.

If $(G_\ell, (v_1, \dots, v_\ell))[v_\ell] = (G_\ell, (v_1, \dots, v_\ell))$, then we say that $(G_\ell, (v_1, \dots, v_\ell))$ is a partial one-component online-LOCAL run of length $\ell$ of $G$. In such case, we call $v_\ell$ the center of the neighborhood.

Finally, we denote by $G_\ell^-$ the disjoint set of partial one-component online-LOCAL runs formed by $v_1, \dots, v_{\ell-1}$, that is, one step shorter than $G_\ell$; this is exactly the information that an online-LOCAL algorithm knows before labeling node $v_\ell$ when $(G_\ell, (v_1, \dots, v_\ell))$ is a partial one-component online-LOCAL run.

**Definition 7.4 (Amnesiac algorithm).** Let A be a deterministic online-LOCAL algorithm, and let us fix the number of nodes to be $n$. We say that A is amnesiac if the following condition is met:

Consider any two graphs $G, H$ of $n$ nodes and any adversarial orderings of the nodes $(v_1, \dots, v_n)$ (for $G$) and $(u_1, \dots, u_n)$ (for $H$). Fix any pair $(i, j) \in [n]^2$ of indices such that

$$ (G_i, (v_1, \dots, v_i))[v_i] = (\bar{G}_i, (v'_1, \dots, v'_k)) \text{ and} \\ (H_j, (u_1, \dots, u_j))[u_j] = (\bar{H}_i, (u'_1, \dots, u'_k)) $$

and are isomorphic (with the isomorphism being order-preserving, i.e., bringing $v'_h$ into $u'_h$, for all $h \in [k]$). Then the outputs of $u_i$ and $v_j$ coincide.

Intuitively, A is amnesiac if the output of A for some node $v$ depends only on the local connected component of the partial online local run and not anything else the algorithm has seen.

In general, an online-LOCAL algorithm uses global memory and hence it is not amnesiac.
## 7.2 Online to amnesiac

We are now ready to generalize the intuition we provided in Section 2.3 for turning any online-LOCAL algorithm into an amnesiac algorithm with the cost of blowing up its locality.

**Lemma 7.5.** Let $\Pi$ be an LCL problem with degree constraint $\Delta$, input label set $\Sigma_{in}$ and output label set $\Sigma_{out}$. Let $\mathcal{A}$ be a deterministic online-LOCAL algorithm solving $\Pi$ over a family $\mathcal{F}$ of graphs that is closed under disjoint graph union and node/edge removal. Assume $\mathcal{A}$ has locality $T(n)$ for an $n$-node graph. Then there exists an amnesiac online-LOCAL algorithm $\mathcal{A}'$ that solves $\Pi$ on an $n$-node graph in $\mathcal{F}$ with locality $T(2^{O(n^3)})$.

*Proof.* Let $T = T(N)$ be the locality of the following experiment; we determine the size $N$ of the experiment graph later. Let $\mathcal{G}_\ell$ be the set of all partial one-component online-LOCAL runs of length $\ell$ for $n$-node graphs in $\mathcal{F}$ (up to isomorphisms). We denote $g_\ell = |\mathcal{G}_\ell|$ and remark that $g_\ell \le g = 2^{n^2}|\Sigma_{in}|^n$. Notice that the term $2^{2n}$ takes into accounts not only all possible topologies (up to isomorphisms), but also all possible orderings of the nodes: indeed, there are at most $2^{2n}$ directed graphs of $n$ nodes where the vertices are labelled with elements of $[n]$ (which defines an ordering). We set $N_\ell = (3|\Sigma_{out}|ng)^{n-\ell+1}n$.

We now adaptively construct an experiment graph $H$ in $n$ phases. In the first phase, we construct $N_1$ copies of all graphs in $\mathcal{G}_1$, that is, we construct $N_1 g_1$ disjoint components describing all possible isolated neighborhoods an online-LOCAL algorithm might see. We then show the centers of these regions to $\mathcal{A}$ and let it label them. As there are $N_1$ copies of each partial online local run of length 1, for each of these, say $\mathcal{T}$, there exists a canonical label $\sigma_{\mathcal{T}}$ that appears at least $N_1/|\Sigma_{out}|$ times, by the pigeonhole principle. We say that such online-LOCAL runs of length 1 are *good*, and ignore the rest.

In each subsequent phase $\ell$, we again construct $N_\ell$ copies of all graphs in $\mathcal{G}_\ell$, with the catch that, for each graph $(G, (v_1, \dots, v_\ell)) \in \mathcal{G}_\ell$ and for each component of $G^-$, we take the corresponding *good* partial one-component online-LOCAL run from a previous phase; we defer arguing why such good runs exist for now. Next we show node $v_\ell$ to $\mathcal{A}$ and let it label the node. Finally, again by the pigeonhole principle, for each partial one-component online-LOCAL run $\mathcal{T}$ (of length $\ell$) we find a canonical label $\sigma_{\mathcal{T}}$ that appears at least $N_\ell/|\Sigma_{out}|$ times, and mark the corresponding runs as good.

Now our new online-LOCAL algorithm $\mathcal{B}$ works as follows: Before even processing the first node of the input, $\mathcal{B}$ runs the above-described experiment by simulating $\mathcal{A}$ on $H$ with locality $T$. Notice that the nodes of the experiment graph will be processed according to a *global ordering* which is *locally consistent* with that of the nodes in the single partial one-component online-LOCAL runs. We do not care about the specific global ordering of the nodes.

When processing node $v$, algorithm $\mathcal{B}$ looks at partial one-component online-LOCAL run around $v$ and finds a corresponding good and unused run from the experiment graph $H$. Algorithm $\mathcal{B}$ labels $v$ with the good label that it found in $H$ and marks the neighborhood in $H$ used.

In each step, algorithm $\mathcal{B}$ can find such unused good neighborhoods as after the whole input has been processed, what the algorithm has seen corresponds to a partial online-LOCAL run, and in particular each component of this run corresponds to a partial one-component online-LOCAL run in $H$. There are at most $n$ such component. By construction, there are at least $N_n$ copies of each type of partial one-component runs in $H$. At least $N_n/|\Sigma_{out}| \gg n$ of those are good, and hence the algorithm can find good and unused neighborhoods for each of the final partial one-component online-LOCAL runs. But as each good run in $H$ is formed by combining only good components in $H$, there must also be a good and unused partial one-component online-LOCAL run corresponding to each processed node $v$. This construction ensures that $\mathcal{B}$ is amnesiac.
Now, by contradiction, assume that $\mathcal{B}$ doesn't solve $\Pi$. Since $\Pi$ is an LCL, there must be a node $v$ of the input graph such that the whole output in its radius-$r$ neighborhood, with $r$ being the checking radius, is not admissible. However, the output of $\mathcal{B}$ in this neighborhood is the output of $\mathcal{A}$ from the experiment graph in a partial one-component online-LOCAL run, which must be correct by the hypothesis.

The only thing left to do is to argue that we can always find a good online-LOCAL run in the construction and to compute the final size of the experiment graph, and hence the locality of $\mathcal{B}$. We start with the former: Consider phase $\ell$. All subsequent phases contain $\sum_{k=\ell+1}^n N_k g_k$ graphs, the simulation uses at most $n$ graphs, and each of those may use at most $n$ previously-used components. Hence, nodes from phase $\ell$ can be used at most

$$n + n \sum_{k=\ell+1}^{n} N_k g_k \leq n + ng \sum_{k=\ell+1}^{n} N_k \leq n + \frac{N_\ell}{2|\Sigma_{\text{out}}|}$$

As $n \ll N_\ell$, we get that

$$\frac{N_\ell}{|\Sigma_{\text{out}}|} \geq n + n \sum_{k=\ell+1}^{n} N_k g_k,$$

that is the future phases won't run out of components.

Finally, the size of the experiment graph is

$$N = n \sum_{\ell=1}^{n} N_{\ell} g_{\ell} \leq N_0 = n(3|\Sigma_{\text{out}}|gn)^{n+1} = n2^{O(n^3)} = 2^{O(n^3)},$$

and it belongs to $\mathcal{F}$ as $\mathcal{F}$ is closed under disjoint graph union and node/edge removal. $\square$

The next lemma shows how to generalize the idea behind Lemma 7.5 all the way up to randomized online-LOCAL.

**Lemma 7.6.** Let $\Pi$ be an LCL problem with degree constraint $\Delta$, input label set $\Sigma_{in}$ and output label set $\Sigma_{out}$. Let $\mathcal{A}$ be a randomized online-LOCAL algorithm solving $\Pi$ over a family $\mathcal{F}$ of graphs that is closed under disjoint graph union and node and edge removals. Assume $\mathcal{A}$ has locality $T(n)$ and success probability $p(n) > 0$ for an $n$-node graph. Then there exists an amnesiac online-LOCAL algorithm $\mathcal{A}'$ that solves $\Pi$ on a graph in $\mathcal{F}$ with $n$ nodes with locality $T(2^{O(n^3)} + 2^{O(2n^2)} \cdot \log \frac{1}{p(n)})$.

Note the locality is such that, if $p(n)$ converges to 1 fast enough, then we only have a $2^{\text{poly}(n)}$ blowup in the locality (instead of a doubly-exponential one).

*Proof.* The main idea is to adapt the proof of Lemma 7.5. The main challenge is that the construction of the simulation graph in the proof of Lemma 7.5 was adaptive to the output of the deterministic online-LOCAL algorithm; however, the adversary in the randomized online-LOCAL model is oblivious to the randomness of the algorithm. In fact only a $q' = 1/|\Sigma_{out}|$ fraction of components in each phase of the proof of Lemma 7.5 are good, and we cannot adaptively choose to use only those.

To combat this, we modify the experiment: instead of adaptively choosing only the good components and discarding the rest, we sample the components from the previous phases uniformly at random without replacement. We later show that the sampled component is good with probability at least $q = q'/2$. In the worst case, each component at layer $N_\ell$ may use up to $n$ partial one-component online-LOCAL runs from the previous layers $N_1, \dots, N_{\ell-1}$, each of which is sampled to be good with probability only $q$. As the construction is $n$ levels deep (i.e., there are $n$ layers $N_1, \dots, N_n$)
and the whole construction needs to work for all up to $g = 2^{n^2}|\Sigma_{in}|^n$ different partial one-component online-LOCAL runs, the total probability of finding a good label in all $N_\ell$, $\ell \in [n]$, is at least $q^{gn^2}$.

This probability is minuscule, but we can boost it by increasing the size of the construction by considering

$$k = 1 + \left[ q^{-2^{n^2}|\Sigma_{in}|^n n^2} \log \frac{1}{p(n)} \right]$$

disjoint copies of the simulation graph independently. Letting $N$ be the size of a single simulation graph, $kN$ is then the size of the whole experiment. Since $N = 2^{O(n^3)}$ in Lemma 7.5, we have

$$kN = 2^{O(n^3)} + 2^{O(2^{n^2})} \log \frac{1}{p(n)}.$$

The probability that each simulation graph does not contain all the necessary good labels in all layers is at most

$$(1 - q^{gn^2})^k \le e^{-kq^{gn^2}} = e^{-kq^{2^{n^2}|\Sigma_{in}|^n n^2}} < p(n).$$

Since the success probability of $\mathcal{A}$ is $p(n)$, by the inclusion-exclusion principle, we get positive probability that at least one simulation graph in the experiment contains all the necessary good labels and, in addition, $\mathcal{A}$ does not fail on it.

We show that the probability of sampling a good component is indeed at least $q = 1/(2|\Sigma_{out}|)$. Consider the components in phase $\ell$. For each component type, there are at least $N_\ell/|\Sigma_{out}|$ that are good. By the calculations in the proof of Lemma 7.5, future layers will use at most $N_\ell/(2|\Sigma_{out}|)$ of them. Hence, after each step, at least $1/(2|\Sigma_{out}|) = q$ fraction of the components are still good and unused, as desired.

We finish the proof by showing that there indeed exists an amnesiac algorithm $\mathcal{A}'$ as in the claim. As argued above, our experiment succeeds with positive probability. After fixing the randomness $f: V(H) \to \{0, 1\}^N$ of the algorithm $\mathcal{A}$, we obtain a uniquely defined deterministic online-LOCAL algorithm $\mathcal{A}[f]$ that behaves exactly as $\mathcal{A}$ when given the random bit string $f$ as input. In particular, for such $f$, the following holds:

1. There exists a simulation graph with the necessary number of good labels in all layers.

2. $\mathcal{A}[f]$ does not fail on the aforementioned simulation graph.

Now the amnesiac algorithm $\mathcal{B}$ works as follows: Since there are finitely many possible simulation graphs and finitely many behaviors of $\mathcal{A}[f]$ (for all possible $f$), $\mathcal{B}$ executes a preprocessing phase in which it goes over all possible simulation graphs and tries all possible deterministic online-LOCAL algorithms (according to some ordering, e.g., lexicographical in the description) until it finds the pair with the properties 1 and 2 above. We take such pair and use the labeling for that component as the base for our amnesiac algorithm. Proceeding as in the proof of Theorem 7.1, we then obtain an amnesiac algorithm that has locality

$$T \left( 2^{O(n^3)} + 2^{O(2^{n^2})} \log \frac{1}{p(n)} \right). \quad \square$$

## 7.3 From online-LOCAL to SLOCAL

We first show how the SLOCAL model can nicely “partition” a rooted forest. The idea is not new and comes from [23, Section 7] where it is directly applied to the LOCAL model; we present here an adaptation to SLOCAL. The definition of rooted forest is given in Section 6. For a rooted forest
<figure><img src="image_6.png" /><figcaption>Figure 3: A (3, 4)-clustering of a rooted tree. The leader nodes are colored and their closed clusters marked with their respective color.</figcaption></figure>

$G = (V, E)$ and each node $v \in V$, we denote by $G_v$ the subtree of $G$ that is rooted at $v$. A root-to-leaf path $v_0v_1...v_k$, where $v_i \in V$ for all $i \in \{0, 1, ..., k\}$, is a path of a rooted tree such that $(v_i, v_{i-1})$ is an edge for all $i \in [k]$; we say that the path *starts* at $v_0$ and *ends* at $v_k$.

**Definition 7.7** (($\alpha, \beta$)-clustering of rooted trees). Let $G = (V, E)$ be a rooted forest. An ($\alpha, \beta$)-clustering of $G$ is a subset $\mathcal{L} \subseteq V$ of leader nodes that contains the root and is such that, for each $v \in \mathcal{L}$, the following properties are met:

1. $G_v$ does not contain elements of $\mathcal{L}$ at levels 1, ..., $\alpha - 1$.

2. Each maximal oriented path in $G_v$ contains exactly one element $u \in \mathcal{L}$ such that $\text{dist}_{G_v}(u, v) \in [\alpha, \beta]$, unless the length of the maximal oriented path is at most $\beta - 1$, in which case there is at most one element of $\mathcal{L}$ in the path (and possibly none).

A *cluster* is a maximally connected component of non-leader nodes. A *closed cluster* is a cluster together with its adjacent leader nodes. See Fig. 3 for an example.

We will combine many SLOCAL algorithms: it is easy to prove that the combination of two SLOCAL algorithms with localities $T_1, T_2$ gives an SLOCAL algorithm with locality $O(T_1 + T_2)$ [38, Lemma 2.3].

**Lemma 7.8.** Let $\alpha \in \mathbb{N}_+$, and let $G = (V, E)$ be a rooted forest. There is an SLOCAL algorithm with locality $O(\alpha)$ that produces an $(\alpha - 1, 2\alpha + 1)$-clustering of $G$.

*Proof.* We combine some SLOCAL algorithms. Consider first the following algorithm $A_1$: Suppose a node $v \in V$ is picked by the adversary and asked to commit to something. For each root-to-leaf path $v_0v_1...v_{2\alpha-1}$ (with $v_0 = v$) that $v$ can distinguish using locality $2\alpha - 1$, in parallel, $v$ precommits
that the node $v_{\alpha-1}$ is the *leader* of the path $v_{\alpha-1}v_{\alpha}\dots v_{2\alpha-1}$ unless there is another precommitment on the path within distance $\alpha$ from $v$.

Next we define an algorithm $\mathcal{A}_2$ that takes as input a rooted forest labelled by $\mathcal{A}_1$: Each node $v$ looks at its radius-$\alpha$ neighborhood and checks if there is some other (unique) node that precommitted for $v$ in the neighborhood. If so, it becomes a leader and stores the path that is under its leadership, otherwise it does nothing.

The final algorithm $\mathcal{A}_3$ takes as input a rooted forest labelled by $\mathcal{A}_2$ and is defined as follows: Each node $v$ becomes a leader if and only if it belongs to an oriented root-to-leaf path $v_0v_1\dots v_{\alpha-1}$, with $v_{\alpha-1} = v$ lead by $v_0$. All other nodes do not output anything, except the root, that becomes a leader.

We now prove that the SLOCAL algorithm $\mathcal{A}$ providing the clustering is the composition of $\mathcal{A}_1$, $\mathcal{A}_2$, and $\mathcal{A}_3$, and has locality $O(\alpha)$.

Notice that the root is a leader thanks to $\mathcal{A}_3$. Property 1 in Definition 7.7 is satisfied due to $\mathcal{A}_3$ as well. Furthermore, for each maximal root-to-leaf path, consecutive leader nodes must be within distance at most $2\alpha + 1$ between each other, unless the path ends with a leaf at distance at most $2\alpha$ from the last leader. In fact, if the distance between consecutive leaders is at least $2\alpha + 2$, or there is only one leader and the path is longer than $2\alpha$ from the last leader, there would be at least one non-leader node that does not see any leader within distance $\alpha$ in the path, which is impossible due to how precommitments are done in $\mathcal{A}_1$. $\square$

We can now prove Theorem 7.1, which we restate here for the reader's convenience:

**Theorem 7.1.** Let $\Pi$ be an LCL problem with degree constraint $\Delta$, input label set $\Sigma_{in}$, output label set $\Sigma_{out}$, and checking radius $r > 0$. In addition, let $\mathcal{A}$ be an online-LOCAL algorithm solving $\Pi$ with locality $T(n)$ over rooted forests. Then the following holds:

1. If $\mathcal{A}$ is deterministic, then there exists a deterministic SLOCAL algorithm solving $\Pi$ with locality $O(r) + T(2^{O(n^3)})$.

2. If $\mathcal{A}$ is randomized and has success probability $p(n) > 0$, then there exists a deterministic SLOCAL algorithm solving $\Pi$ with locality $O(r) + T(2^{O(n^3)} + 2^{O(2^{n^2})} \cdot \log \frac{1}{p(n)})$.

*Proof.* Let $G$ denote the input graph, which is a rooted forest, and assume $\mathcal{A}$ is a deterministic online-LOCAL algorithm. We can apply Lemma 7.5 to get an amnesiac algorithm $\mathcal{A}'$ that solves $\Pi$ with locality $T'(n) = T(2^{O(n^3)})$. We now show how to get an SLOCAL algorithm $\mathcal{B}$ solving the problem with roughly the same locality. $\mathcal{B}$ is the composition of four different SLOCAL algorithms $\mathcal{B}_1, \mathcal{B}_2, \mathcal{B}_3, \mathcal{B}_4$, each of them having locality $O(T')$:

1. We first use Lemma 7.8 with $\alpha = 10T' + 4r$, where $r$ is the checking radius of $\Pi$, and obtain an algorithm $\mathcal{B}_1$ that outputs an $(\alpha - 1, 2\alpha + 1)$-clustering of $G$ with locality $O(\alpha)$.

2. Now consider an algorithm $\mathcal{B}_2$ with locality $2\alpha + 4r$ that takes as input $G$ as labelled by $\mathcal{B}_1$ and works as follows: When processing a leader node $v$, it collects the topology of the radius-$2r$ neighborhood of the set composed of the closest leaders $v$ sees in each root-to-leaf path. Then, $v$ runs $\mathcal{A}'$ in this neighborhood and precommits a solution to the LCL for the nodes in such neighborhood. If $v$ is the root, it also presents its own radius-$2r$ neighborhood to $\mathcal{A}'$ and precommits a solution for the whole neighborhood. Observe that all such neighborhoods are disjoint by construction of the $(\alpha - 1, 2\alpha + 1)$-clustering.

3. $\mathcal{B}_3$ also has locality $2\alpha + 4r$ and just makes all nodes whose label has been precommitted by some other node actually output the precommitted label. (The output of $\mathcal{B}_2$ guarantees there are no conflicts to be resolved.)
4. Finally, $\mathcal{B}_4$ has again locality $2\alpha + 4r$ and just brute-forces a solution in each cluster. The solution is guaranteed to exist because $\mathcal{A}'$ was run in all disjoint neighborhoods and works correctly. In fact, $\mathcal{B}_4$ can just continue calling $\mathcal{A}'$ on each cluster it sees.

The combination of $\mathcal{B}_1, \mathcal{B}_2, \mathcal{B}_3$, and $\mathcal{B}_4$ yields a deterministic SLOCAL algorithm $\mathcal{B}$ that has locality $O(\alpha) = O(r) + O(T'(n))$.

The same argument applies to a randomized online-LOCAL algorithm, the only change is that now $T'$ is $T'(n) = T(2^{O(n^3)} + 2^{O(2^{n^2})} \cdot \log \frac{1}{p(n)})$. $\square$

## 7.4 From SLOCAL to LOCAL

It is folklore that all LCL problems that have complexity $O(1)$ in SLOCAL belong to the complexity class $O(\log^* n)$ in LOCAL. Then, to obtain Theorem 1.5, it suffices to show that all LCLs with complexity $o(\log n)$ in SLOCAL in rooted trees actually belong to the complexity class $O(1)$. We restate Theorem 7.2.

**Theorem 7.2.** Let $\mathcal{A}$ be an SLOCAL algorithm solving an LCL problem $\Pi$ that runs with locality $o(\log_{\Delta} n)$ over rooted forests of maximum degree $\Delta$ and $n$ nodes. Then, there exists an SLOCAL algorithm $\mathcal{B}$ solving $\Pi$ with locality $O(1)$.

*Proof.* Assume $\Pi$ has checking radius $r \ge 0$, and $T(n) = o(\log_{\Delta} n)$ to be the locality of $\mathcal{A}$. Furthermore, w.l.o.g., suppose $T(n) \ge r$ for all $n$ large enough. Let $N$ be a large enough integer such that $T(N) = k \ge r$. Let $G$ be a rooted tree of maximum degree $\Delta$ with $n$ nodes. We now construct a new SLOCAL algorithm $\mathcal{B}$ which is the composition of many SLOCAL algorithms.

For the first SLOCAL algorithm $\mathcal{B}_1$, we make use of Lemma 7.8 where $\alpha = \lfloor(\log_{\Delta} N - 2)/4\rfloor$. Hence, $\mathcal{B}_1$ yields an $(\alpha - 1, 2\alpha + 1)$-clustering of $G$ in time $O(\alpha)$, with $\alpha - 1 \ge (\log_{\Delta} N - 10)/4$ and $2\alpha + 1 \le (\log_{\Delta} N)/2$. Hence, any closed cluster will have at most $\Delta^{2\alpha+1} \le \sqrt{N}$ nodes (including the adjacent leader nodes).

Then, we consider a second SLOCAL algorithm $\mathcal{B}_2$ that takes $G$ and the $(\alpha - 1, 2\alpha + 1)$-clustering of $G$ in input and reassigns identifiers from the set $[N]$ “locally”. To better describe how $\mathcal{B}_2$ works, let us define some notation. For each leader node $v$, let $\mathcal{C}_v$ denote the closed cluster where $v$ is the leader node of minimum level, and let $\mathcal{L}_v$ be the set of leader nodes in $\mathcal{C}_v$ except for $v$. Consider a partition of the nodes in $(\mathcal{C}_v \setminus \mathcal{N}_k(v)) \cup \mathcal{N}_k(\mathcal{L}_v)$ according to their distance from $v$. More specifically, $\mathcal{C}_v^{(1)}$ contains all nodes that have distance between $k+1$ and $\lfloor(\alpha-1)/4\rfloor$ from $v$, while, for $i \in \{2, 3\}$, $\mathcal{C}_v^{(i)}$ contains nodes that have distance between $\lfloor(\alpha-1)/(6-i)\rfloor + 1$ and $\lfloor(\alpha-1)/(5-i)\rfloor$ from $v$. Finally, $\mathcal{C}_v^{(4)}$ contains all the other nodes in $\mathcal{C}_v$, which have distance at least $\lfloor(\alpha-1)/2\rfloor + 1$ from $v$. Notice that $|\{(\mathcal{C}_v \setminus \mathcal{N}_k(v)) \cup \mathcal{N}_k(\mathcal{L}_v)\}| \le \Delta^{2\alpha+1+k} \le \Delta^{(\log_{\Delta} N)/2+o(\log_{\Delta} N)} \le N^{2/3}$ for $N$ large enough. Then, $\mathcal{B}_2$ works as follows: When a non-leader node is picked by the adversary, nothing happens. When a leader node $v$ is selected, it precommits identifiers for the nodes in $(\mathcal{C}_v \setminus \mathcal{N}_k(v)) \cup \mathcal{N}_k(\mathcal{L}_v)$. In details, it assigns identifiers from $1$ to $\lfloor N/4 \rfloor$ to nodes in $\mathcal{C}_v^{(1)}$, from $\lfloor N/4 \rfloor + 1$ to $\lfloor N/2 \rfloor$ to $\mathcal{C}_v^{(3)}$, from $\lfloor N/2 \rfloor + 1$ to $\lfloor 3N/4 \rfloor$ to $\mathcal{C}_v^{(2)}$, from $\lfloor 3N/4 \rfloor + 1$ to $N$ to $\mathcal{C}_v^{(4)}$. Notice that, since $|\mathcal{C}_v^{(i)}| \le N^{2/4}$, then even $\lfloor N/5 \rfloor$ distinct identifiers are enough to cover the whole region $\mathcal{C}_v^{(i)}$ when $N$ is large enough. Furthermore, if $v$ is the root of the whole graph, it precommits distinct identifiers from the set $\{\lfloor 3N/4 \rfloor + 1, \dots, N\}$ for the nodes that have distance at most $k$ from $v$ (v itself included).

The third and last SLOCAL algorithm $\mathcal{B}_3$ takes as input the whole rooted tree with the clustering given by $\mathcal{B}_1$ and the output of leader nodes given by $\mathcal{B}_2$, and computes the solution to the problem as follows: Every node $u$ (that does not belong to $\mathcal{C}_v$ where $v$ is the root of the graph) looks at its two closest leader nodes $v_u^{(1)}$ (the closest one) and $v_u^{(2)}$ (the second closest one) that are ancestors
(if $u$ is a leader, it still looks up in the tree for two different leader ancestor), and collects all the information regarding identifiers for $G[\mathcal{N}_k(C_{v_u^{(1)}})]$. In this way, $u$ can locally simulate $\mathcal{A}$ on a "virtual graph" $G_u = G[\mathcal{N}_k(C_{v_u^{(1)}})]$ with $|\mathcal{N}_k(C_{v_u^{(1)}})| \le N$ nodes. The adversarial ordering according to which $\mathcal{A}$ processes $G_u = G[\mathcal{N}_k(C_{v_u^{(1)}})]$ is induced by the ordering of the identifiers. Notice that it might still be that $\mathcal{A}$ processes two nodes at the same time but, due to the assignment of identifiers done by $B_2$, the outputs of these nodes can be determined independently of each other. Then, $u$ outputs whatever $\mathcal{A}$ outputs on $u$ according to this simulation. If $u$ is the root of the whole graph, then it knows already the all the identifiers needed to run $\mathcal{A}$ in $G[\mathcal{N}_k(C_u)]$. If $u$ is in $C_v$ and $C_v$ is the cluster of the root node of the graph, then by accessing the memory of $v$ it gets access to all the information it needs to compute its output.

Notice that each $B_i$ has locality $O(\alpha)$, hence the whole algorithm $\mathcal{B}$ obtained by the composition of $B_1$, $B_2$, and $B_3$ has locality $O(\alpha)$ by [38, Lemma 2.3]. Observe also that $O(\alpha) = O(\log_{\Delta} N) = O(1)$.

Also, the final output of $\mathcal{B}$ is correct: Suppose, by contradiction, that there is a failure somewhere, that is, a node $v$ could detect its neighborhood $\mathcal{N}_r(v)$ as non-admissible. Suppose $v$ does not belong $C_u$ where $u$ is the root of the graph, and denote its two closest ancestors that are leader nodes by $v_u^{(1)}$ (the closest one) and $v_u^{(2)}$ (the second closest one). We have two cases. If $u \in C_{v_u^{(2)}}^{(4)} \cup C_{v_u^{(1)}}^{(1)} \cup C_{v_u^{(1)}}^{(2)}$, then its output must be correct: it is completely determined by $G[\mathcal{N}_k(C_{v_u^{(1)}} \cap (C_{v_u^{(2)}}^{(4)} \cup C_{v_u^{(1)}}^{(1)} \cup C_{v_u^{(1)}}^{(2)}))]$ which contains only distinct identifiers (because it is a subgraph of $G[C_{v_u^{(2)}}^{(4)} \cup C_{v_u^{(1)}}^{(1)} \cup C_{v_u^{(1)}}^{(2)} \cup C_{v_u^{(1)}}^{(3)}]$) and hence can be extended to a valid input for $\mathcal{A}$ with $N$ nodes (choosing identifiers arbitrarily in $[N^2] \setminus [N]$ and extending the adversarial processing order respecting the ordering induced by identifiers). In the second case, $u \in C_{v_u^{(1)}}^{(3)} \cup C_{v_u^{(1)}}^{(4)}$. Also in this case the output of $u$ must be correct: it is completely determined by $G[\mathcal{N}_k(C_{v_u^{(1)}} \cap (C_{v_u^{(1)}}^{(3)} \cup C_{v_u^{(1)}}^{(4)}))]$ which contains only distinct identifiers (because it is a subgraph of $G[C_{v_u^{(1)}}^{(2)} \cup C_{v_u^{(1)}}^{(3)} \cup C_{v_u^{(1)}}^{(4)}]$) and hence can be extended to a valid input for $\mathcal{A}$ with $N$ nodes (choosing identifiers arbitrarily in $[N^2]$ and extending the adversarial processing order respecting the ordering induced by identifiers). An analogous argument holds for nodes in $C_v$ where $v$ is the root node of the graph. $\square$

# 8 Lower bound for 3-coloring grids in randomized online-LOCAL

In this section, we will show that 3-coloring $(\sqrt{n} \times \sqrt{n})$-grids in randomized online-LOCAL requires $\Omega(\log n)$-locality:

**Theorem 8.1.** *The locality of a randomized online-LOCAL algorithm for solving 3-coloring in $(\sqrt{n} \times \sqrt{n})$-grids is $\Omega(\log n)$.*

We will base our proof on the recent result of Chang et al. [22], where the authors show a similar lower bound for the deterministic online-LOCAL model. We will start with a brief overview of the techniques used in [22].

## 8.1 Relevant ideas from Chang et al. [22]

The lower bound in [22] is based on the idea that any coloring of a grid $G$ with the three colors $\{1, 2, 3\}$ can be partitioned into regions with colors 1 and 2 that are separated by boundaries of color 3. Formally, a region is a maximal connected component that is colored only with colors 1 and 2, while a boundary is a maximal connected component in $G^2$ that is colored only with color 3. It
<figure><img src="image_7.png" /><figcaption>Figure 4: Example of a 3-colored grid with two boundaries $B_1$ and $B_2$ that have different parities. As one can see, $b(u, v) = 2$: No matter if we take the blue or the red path from $u$ to $v$, we always cross $B_1$ and then $B_2$.</figcaption></figure>

is crucial to observe that the boundaries of color 3 are not always compatible and that they have parities of their own (see Fig. 4). Indeed, the core idea of the proof is to constrict many incompatible boundaries of color 3 to a small space, thus requiring a view of $\Omega(\log n)$ to resolve them.

Using the same terminology as [22], we count incompatible boundaries between two points by using so-called a- and b-values. The a-value is defined as an edge weight between any two nodes and captures the change of colors 1 and 2.

**Definition 8.2 (a-value [22]).** Given a directed edge $(u, v)$ and a 3-coloring of the nodes $c: V \to \{1, 2, 3\}$, we define

$$a(u, v) = \begin{cases} c(u) - c(v), & \text{if } c(u) \neq 3 \text{ and } c(v) \neq 3 \\ 0, & \text{otherwise.} \end{cases}$$

Observe that the a-value of any directed 4-cycle in a grid is equal to 0. Using the a-value, we define the b-value of a path.

**Definition 8.3 (b-value [22]).** For a directed path $P$, its b-value is defined as

$$b(P) = \sum_{(u,v) \in H} a(u, v).$$

On a high level, the b-value of a path describes the cumulative total of incompatible boundaries along this path. Note we say “cumulative” because in this count boundaries of the same parity cancel each other out. Indeed, if we consider the b-value of a simple directed cycle in a grid, then it must be equal to 0:

**Lemma 8.4 (b-value of a cycle is zero [22]).** Let $C$ be a directed cycle in $G$. Then $b(C) = 0$.

As an example, observe that a path that starts and ends with color 3 and otherwise is colored with colors 1 and 2 always has a b-value of 0 or 1. In particular, the b-value is 1 if the distance between the nodes of color 3 is even (and thus the boundaries are incompatible). Meanwhile, a path that goes through two incompatible regions has a total b-value of 2. Nevertheless, a path going through two boundaries that are compatible has a total b-value of 0.
**Lemma 8.5** (Parity of the b-value [22]). Let P denote any directed path of length ℓ that starts in node u and ends in node v in a grid. Then, the parity of b(P) is

$$b(P) \equiv \beta(u) + \beta(v) + \ell \pmod{2}$$

where β is an indicator variable stating whether a node is of color 3 or not:

$$\beta(u) = \begin{cases} 1, & \text{if } c(u) = 3 \\ 0, & \text{otherwise.} \end{cases}$$

Observe that the parity of the b-value of a path is determined by the colors of the endpoints of this path.

## 8.2 From deterministic to randomized online-LOCAL

Suppose that we are given a randomized online-LOCAL algorithm with visibility radius $T = o(\log n)$. Our goal is to prove the algorithm fails to solve the 3-coloring problem. Using Yao's minimax principle, we show how to construct an (oblivious) adversarial distribution of inputs so that any deterministic online-LOCAL algorithm fails with noticeable probability.

As in [22], the lower bound consists of two main steps:

1. First we show how to force paths to have an arbitrarily large b-value. Generally we cannot force a large b-value between the path's endpoints (or in fact between any two fixed nodes), but we do get the guarantee that it contains two nodes $v_1$ and $v_2$ where $b(v_1, v_2)$ is large. Note the location of $v_1$ and $v_2$ is completely unknown to us since we are working with an oblivious adversary. The construction is inductive: Given a procedure that generates a path with b-value $\ge k-1$ with probability $\ge 1/2$, we show how to generate a path with b-value $\ge k$ also with probability $\ge 1/2$. (Cf. the construction in [22] with an adaptive adversary, which succeeds every time.) Since we invoke the construction for $k-1$ a constant number of times, we are able to obtain any desired b-value of $k = o(\log n)$ with high probability. Note it is logical that we cannot do much better than this as it would contradict the existing $O(\log n)$ deterministic online-LOCAL algorithm.

2. The second step is to actually obtain a contradiction. (See Fig. 5.) First we construct a path $P_1$ with large b-value, say $\gg 4T$, between nodes $u_s$ and $v_t$. To get the contradiction, we wish to place two nodes $w_s$ and $w_t$ next to $u_s$ and $v_t$, respectively, so that the four node cycle has positive b-value (which is impossible due to Lemma 8.4). If we had an adaptive adversary as in [22], this would be relatively simple: Since the adaptive adversary knows the location of $u_s$ and $v_t$, it just constructs an arbitrary path $P_2$ with the same size as $P_1$, picks any two $w_s$ and $w_t$ that are at the same distance from each other as $u_s$ and $v_t$, mirrors $P_2$ if needed to obtain a non-negative b-value, and then places this at minimal distance to $P_1$. We show that, allowing for some failure probability, we do not need any information about $u_s$ and $v_t$ (i.e., nor their location nor the distance between them) in order to obtain the same contradiction.

We now proceed with the proof as outlined above. Accordingly, the first step is the following:

**Lemma 8.6.** Given any $k = o(\log n)$, there is an adversarial strategy to construct a directed path of length $n^{o(1)}$ with a b-value of at least $k$ against any online-LOCAL algorithm with locality $T = o(\log n)$. Moreover, this strategy succeeds with high probability.

*Proof.* Consider the following recursive construction:
* If $k = 0$, create a single node with previously unrevealed nodes all around it (inside the visibility radius $T$).

* Otherwise, repeat the following steps four times in total:

- Create four distinct paths $P_1, P_2, P_3, P_4$ by following the procedure for $k-1$.

- Toss independent fair coins $c_1, c_2, c_3 \in \{0, 1\}$.

- Connect the $P_i$'s horizontally aligned and in order while placing $c_i + 1$ nodes between paths $P_i$ and $P_{i+1}$.

Let $Q_1, Q_2, Q_3, Q_4$ be the four paths created by this procedure (each having their own four $P_i$'s coming from the procedure in the previous iteration $k-1$). Next, we connect the $Q_i$'s horizontally aligned with each other and in arbitrary order. Note that we need to place an additional node between each pair of $Q_i$'s. Otherwise, we would have to have revealed the edge between the two endpoints too early to the algorithm.

Thus, for $k \ge 1$ we have 16 invocations of the procedure for $k-1$ in total. We argue that, with probability at least $1/2$, the path yielded by this procedure contains a segment with $b$-value at least $k$. By repeating this procedure $O(\log n)$ times independently, we obtain at least one path with the desired property with high probability.

To prove that the recursive construction works, we proceed by induction. Fix $k \ge 1$ and suppose that the procedure for $k-1$ succeeds with probability $p \ge 1/2$ at yielding a segment with $b$-value at least $k-1$. Let us first consider $Q_1$. Let $X_i$ be a random variable that is 1 if this occurs for path $P_i$ and 0 otherwise. Then we have

$$ 
\begin{aligned}
\Pr\left[\sum_{i=1}^{4} X_i < 2\right] &= \Pr\left[\sum_{i=1}^{4} X_i = 0\right] + \Pr\left[\sum_{i=1}^{4} X_i = 1\right] \\
&= (1-p)^4 + 4p(1-p)^3 \\
&= (1-p)^3(1+3p) \\
&\le \frac{1}{2}.
\end{aligned}
$$

Hence, with probability at least $1/2$ there are at least two paths $P_i$ and $P_j$, $i < j$, for which the construction succeeds.

Since we are dealing with paths, we may simplify the notation and write $b(u, v)$ for the $b$-value of the (unique) segment that starts at $u$ and ends at $v$. Let thus $u_i, v_i, u_j, v_j$ appear in this order in $Q_1$ and $|b(u_i, v_i)|, |b(u_j, v_j)| \ge k-1$. Next we will show that, conditioned on this assumption, the probability that $Q_1$ contains a segment with $b$-value at least $k$ is at least $1/2$. Hence, a priori, $Q_1$ contains such a segment with probability at least $1/4$. Since all $Q_i$'s are constructed the in the same way and independently of one another, the probability that at least one of the $Q_i$'s contains such a segment is at least $1 - (1 - 1/4)^4 > 1 - 1/e > 1/2$.

Let us write $\sigma(x)$ for the sign function of $x$ (i.e., $\sigma(x) = 1$ if $x > 0$, $\sigma(x) = -1$ if $x < 0$, and $\sigma(0) = 0$). To see why the above holds for $Q_1$, consider the two following cases:

**Case 1:** $\sigma(b(u_i, v_i)) = \sigma(b(u_j, v_j))$. Using Lemma 8.5, we have that $b(v_i, u_j) \equiv \beta(v_i) + \beta(u_j) + c_i + \cdots + c_{j-1} \pmod 2$. Since $\beta(v_i)$ and $\beta(u_j)$ are fixed, and the coin tosses are independent, we have $|b(v_i, u_j)| \neq k-1 \pmod 2$ with probability $1/2$. Assuming this holds, we have either
$|b(v_i, u_j)| \ge k$, in which case we are done, or $|b(v_i, u_j)| \le k - 2$. Since $b(u_i, v_i)$ and $b(u_j, v_j)$ have the same sign, we have

$$ 
\begin{aligned}
|b(u_i, v_j)| &= |b(u_i, v_i) + b(v_i, u_j) + b(u_j, v_j)| \\
&\ge |b(u_i, v_i) + b(u_j, v_j)| - |b(v_i, u_j)| \\
&\ge 2(k-1) - (k-2) \\
&= k.
\end{aligned}
$$

**Case 2:** $\sigma(b(u_i, v_i)) \neq \sigma(b(u_j, v_j))$. Arguing by using Lemma 8.5 as before, we obtain that $|b(v_i, u_j)| \neq 0 \pmod 2$ holds with probability $1/2$. Assuming this is the case, we have thus $|b(v_i, u_j)| \ge 1$. Without restriction, let $\sigma(b(u_i, v_i)) = \sigma(b(v_i, u_j))$. Then

$$ |b(u_i, u_j)| = |b(u_i, v_i) + b(v_i, u_j)| \ge k - 1 + 1 = k. $$

Finally, let us confirm that the construction fits into the $(\sqrt{n} \times \sqrt{n})$-grid. We only reveal at most $2T + 1 = o(\sqrt{n})$ in a column, so we need to only consider nodes along a row. The initial path contains $m_0 = 2T + 1$ visible nodes and in the $i$-th recursive step we have $m_i \le 16p_{i-1} + 27$ visible nodes in total for $i \ge 1$. (Inside each $Q_i$ we need at most $2(4-1) = 6$ additional nodes to join the four $P_i$'s, and to join the four $Q_i$'s we need an additional 3 nodes.) Solving the recursion, in the $k$-th step we have thus

$$ m_k = \frac{1}{5} \left( 2^{4k+1}(5T+7) - 9 \right) = n^{o(1)} $$

visible nodes along the path since $k, T = o(\log n)$. $\square$

We now illustrate the idea for getting the contradiction previously described. (See Fig. 5.) Invoking Lemma 8.6, we obtain a path $P_1$ with a $b$-value of $4T + 4$ between two nodes $u_s$ and $v_t$ (whose positions are unknown to us). Letting $L$ be the length of $P_1$, we (arbitrarily) create a second path $P_2$ of length $10L$ and then randomly choose how to align $P_1$ and $P_2$. More specifically, letting $u$ be the first node in $P_1$, we choose some node $w$ of $P_2$ uniformly at random and align $u$ and $w$; then we mirror $P_2$ with probability $1/2$ and reveal it at distance $2T + 2$ to $P_1$ (which is consistent with all previously revealed nodes).

The reason why this works is the following: Since $P_1$ has length $L$ and $P_2$ length $10L$, with at least $4/5$ we align the paths so that each node in $P_1$ has a matching node underneath it in $P_2$. Let $w_s$ and $w_t$ be the nodes matching $u_s$ and $v_t$, respectively. Then because we mirror $P_2$ with probability $1/2$, we get that $b(w_s, \dots, w_t)$ is at least zero in expectation (conditioned on having properly aligned the two paths). Hence, with probability at least $2/5$ we obtain a cycle $(u_s, \dots, v_t, \dots, w_t, \dots, w_s, \dots, u_s)$ where $b(u_s, \dots, v_t) > 4T + 4$, $b(w_t, \dots, w_s) \ge 0$, and $b(v_t, \dots, w_t), b(w_s, \dots, u_s) \ge -2T - 2$ (due to the distance between the two paths).

*Proof of Theorem 8.1.* Observe that, using Lemma 8.6, we can construct a path $P_1 = (u_0, \dots, u_L)$ of length $L = n^{o(1)}$ where some segment $(u_s, \dots, u_t)$ of $P_1$ has a $b$-value of $k > 4T + 4$. Next we construct a path $P_2 = (v_0, \dots, v_{10L})$ of length $10L$ that will be placed below $P_1$. We assume that the points of the path are revealed to the algorithm in some predefined order.

The position and orientation of $P_2$ are chosen as follows:

1. Choose a node $v_r \in [L, 9L]$ of $P_2$ uniformly at random. This node is placed below the node $u_0$ of $P_1$ at $2T + 2$ distance from it.

2. Throw a fair coin $m \in \{0, 1\}$. If $m = 1$, mirror $P_2$ along the vertical axis that goes through $u_0$ and $v_r$.
<figure><img src="image_8.png" /><figcaption>Figure 5: How to turn paths with large b-value into a contradiction. Here the blue area includes the nodes revealed so far around the path segments ($u_0, \dots, u_L$) and the corresponding part of $P_2$ underneath it. The green segments are the two segments we consider in the proof. A cycle going through both paths leads to a contradiction.</figcaption></figure>

The nodes of $P_2$ are revealed to the algorithm in the same predefined and possibly mirrored order. See Fig. 5 for an example.

We next prove that we obtain the desired lower bound. First notice that, since we pick $v_r \in [L, 9L]$, every node in $P_1$ has a counterpart in $P_2$ whether we mirror $P_2$ or not. Let ($w_s, \dots, w_t$) denote the segment matched to ($u_s, \dots, u_t$). Consider the case where either of the following is true:

* $m = 0$ and $r \in [L, 9L - s - t]$

* $m = 1$ and $r \in [L + s + t, 9L]$

Denoting by $E$ the event in which this occurs, note we have

$$ \Pr[E] = \frac{1}{2} \Pr[r \in [L, 9L - s - t]] + \frac{1}{2} \Pr[r \in [L + s + t, 9L]] = \frac{8L - s - t + 1}{9L + 1} \geq \frac{6L + 1}{9L + 1} > \frac{2}{3}. $$

Now conditioned on $E$, notice that every segment ($v_x, \dots, v_y$) where $x \in [L + s, 9L - s]$ and $y \in [L + t, 9L - t]$ has equal probability of being matched with ($u_s, \dots, u_t$) either in the same direction (i.e., $w_s = v_x$ and $u_t = v_y$) or reversed (i.e., $w_s = v_y$ and $w_t = v_x$). Hence,

$$ \Pr[b(w_t, \dots, w_s) \geq 0 | E] \geq \frac{1}{2}. $$

(In fact, the probability is exactly $1/2$ if $b(w_t, \dots, w_s) > 0$ and $1$ if $b(w_t, \dots, w_s) = 0$.) Thus, the probability that $b(w_t, \dots, w_s) \geq 0$ is $> (2/3) \cdot (1/2) = 1/3$.

From here on, we proceed as in [22]. By Lemma 8.4, the cycle ($u_s, \dots, u_t, \dots, w_t, \dots, w_s, \dots, u_s$) must have a b-value of 0. However, recall that the b-value of a path is bounded by its length by definition. In our case, $-2T - 2 < b(u_t, \dots, w_t) < 2T + 2$, $-2T - 2 < b(w_s, \dots, u_s) < 2T + 2$, $b(u_s, \dots, u_t) \geq k$, and $b(w_t, \dots, w_s) \geq 0$. In order for the b-value of the cycle to be 0, we would need to have $2(2T + 2) \geq k$, which is a contradiction. Since this occurs with noticeable probability (i.e., $> 1/3$), the claim follows. $\square$

# 9 Dynamic-LOCAL derandomizes LOCAL and breaks symmetry

This section presents a derandomization result for the dynamic-LOCAL model: we show that not only dynamic-LOCAL can simulate randomized LOCAL with no overhead in the locality, but actually it brings the complexity class $O(\log^* n)$ in randomized LOCAL down to $O(1)$.
We make use of the method of conditional expectations from [39] to derandomize the model of dynamic-LOCAL computation. We note that while the following theorems are proven for the class of all graphs, they can be extended to any subclass of graphs.

**Theorem 9.1.** Let $\Pi$ be an LCL problem, and let $\mathcal{A}$ be a randomized LOCAL algorithm solving $\Pi$ with locality $T(n)$ and probability $p > 1 - 1/n$. Then there exists a deterministic dynamic-LOCAL algorithm $\mathcal{A}'$ solving $\Pi$ with locality $O(T(n))$.

*Proof.* The randomized LOCAL algorithm $\mathcal{A}$ can be viewed as a deterministic LOCAL algorithm which is given i.i.d. random variables $R_v$ locally for each node $v$. We show that there exists a dynamic-LOCAL algorithm with locality $O(T(n))$ that assigns fixed values $\rho_v$ for each $R_v$ such that when $\mathcal{A}$ is run on these values as $R_v$, it produces a correct output for problem $\Pi$. Such dynamic-LOCAL clearly implies an $O(T(n))$-locality dynamic-LOCAL algorithm for problem $\Pi$ as one can compose it with $\mathcal{A}$. The proof uses a technique similar to that of derandomizing LOCAL algorithms in SLOCAL [39].

We use the method of conditional expectation. Let $F_v$ be a flag that is 1 when the output around node $v$ is invalid, and 0 otherwise. Note that $F_v$ depends only on the radius-$r$ neighborhood of node $v$. Let $F = \sum_{v \in V} F_v$. As $\Pi$ is an LCL problem, $F = 0$ iff the labeling is correct for the whole graph, and otherwise $F \ge 1$. By definition, $\mathbb{E}[F] = \sum_{v \in V} \mathbb{E}[F_v] \le n(1-p) < 1$.

Let $\sigma = e_1, e_2, \dots, e_m$ be the order of edges in which the adversary dynamically modifies the graph, and let $G_i$ be the graph after modification $i$. Note that any edge can appear multiple times in the sequence if the adversary also removes edges.

Now algorithm $\mathcal{A}'$ sets the randomness as follows: In step $i$, algorithm $\mathcal{A}'$ first clears $\rho_u$ for all nodes $u$ with $\text{dist}(u, e_i) \le T(n) + r$. Then

$$ \mathbb{E}[F \mid \bigwedge_{u, \text{dist}(u, e_i) > T(n) + r} R_u = \rho_u] < 1 $$

as

$$ \mathbb{E}[F \mid \bigwedge_u R_u = \rho_u] < 1 $$

in the previous step. Hence, there exists some concrete values for $\rho_u$ for $\text{dist}(u, e_i) \le T(n) + r$ such that $\mathbb{E}[F \mid \bigwedge_u R_u = \rho_u] < 1$. Algorithm $\mathcal{A}'$ sets all $\rho_u$ to such values. Finally, algorithm $\mathcal{A}'$ simulates $\mathcal{A}$ for all nodes within radius $T(n) + r$ from $e_i$ with randomness fixed at $\rho$.

This produces a correct labeling for all nodes as $\mathbb{E}[F \mid \bigwedge_u R_u = \rho_u] < 1$, and hence

$$ \mathbb{E}[F \mid \bigwedge_u R_u = \rho_u] = 0. \quad \square $$

**Theorem 9.2.** Let $\Pi$ be an LCL problem, and let there exist a randomized LOCAL algorithm solving it with locality $O(\log^* n)$. Then there exists a dynamic-LOCAL algorithm solving $\Pi$ with locality $O(1)$.

*Proof.* Using [21], a randomized LOCAL algorithm for solving $\Pi$ with locality $O(\log^* n)$ implies the existence of a deterministic LOCAL algorithm solving $\Pi$ with locality $O(\log^* n)$. Moreover, the deterministic LOCAL algorithm can be normalized into an algorithm that first finds a distance-$k$ coloring with $O(\Delta^k)$ colors for some constant $k$, and then applies an $O(k)$-locality LOCAL algorithm $\mathcal{A}$ on this coloring.

The dynamic-LOCAL algorithm for solving $\Pi$ maintains a distance-$k$ coloring with $O(\Delta^k)$ colors on the graph, and then applies $\mathcal{A}$ on these colors. When the dynamic-LOCAL algorithm encounters an update, it first clears the colors of all nodes within distance $k$ from the update, and greedily
assigns new colors for those nodes. The greedy assignment always succeeds since each node can have at most $\Delta^k$ neighbors within distance $k$ hence they can use at most $\Delta^k$ of the available colors. Finally, the algorithm applies $\mathcal{A}$ on all nodes of the graph. As $\mathcal{A}$ is a deterministic LOCAL algorithm with locality $O(k)$, and only the colors of nodes within distance $k$ of the update have changed, we have that only the output of nodes within distance $O(k) = O(1)$ from the update change. $\square$

# 10 Randomized online-LOCAL with an adaptive adversary

This section aims at showing that randomized online-LOCAL with an adaptive adversary is as strong as its deterministic counterpart. The proof is very similar to the proof of Theorem 9.1 and uses, again, the method of conditional expectations. Also, as in the previous section, the results can be extended to any subclass of graphs.

**Theorem 10.1.** Let $\Pi$ be an LCL problem, and let $\mathcal{A}$ be an online-LOCAL algorithm with an adaptive adversary solving $\Pi$ with locality $T(n)$ and probability $p > 1 - 1/n$. Then there exists a deterministic online-LOCAL algorithm $\mathcal{A}'$ solving $\Pi$ with locality $T(n)$.

*Proof.* Let $\mathcal{A}$ be an algorithm in the online-LOCAL model with an adaptive adversary and with round complexity $T(n)$. We construct a deterministic online-LOCAL algorithm $\mathcal{A}'$ with the same round complexity $T(n)$ as follows: The algorithm $\mathcal{A}'$ simulates $\mathcal{A}$ with certain fixed random-bit-strings. In particular, whenever new nodes arrive at the input, the algorithm $\mathcal{A}'$ fixes the random bits in all newly arrived nodes in the way we describe below.

We view a run of an online-LOCAL algorithm with an adaptive adversary as a game between an algorithm $\mathcal{A}$ and an adversary. In each step of that game, first the adversary chooses a set of nodes that arrive at the input (one special node and its neighborhood). Then the algorithm $\mathcal{A}$ samples the random bits of the newly arrived nodes and fixes the label of the arrived node. After $i$ steps of this game, we use $\mathcal{F}$ to denote the event that the adversary wins the game, that is algorithm $\mathcal{A}$ produces an invalid output according to problem $\Pi$. By definition, we have $\Pr[\mathcal{F}] \le 1/n$. Here and from now on, the probability expressions assume that the adversary maximizes the probability of $\mathcal{F}$ happening.

Our algorithm $\mathcal{A}'$ in each $i$-th step fixes the random bits of the newly arrived nodes in a way that guarantees that

$$ \Pr[\mathcal{F}|B_1 = b_1, \dots, B_i = b_i] \le \Pr[\mathcal{F}|B_1 = b_1, \dots, B_{i-1} = b_{i-1}]. $$

Here, $B_j = b_j$ stands for fixing the values of random bits of nodes that arrived in the $j$-th step to $b_j$. We note that this can always be done since, by definition, we have

$$ \Pr[\mathcal{F}|B_1 = b_1, \dots, B_{i-1} = b_{i-1}] = \mathbb{E}_{B_i} [\Pr[\mathcal{F}|B_1 = b_1, \dots, B_i = b_i]]. $$

Moreover, the online-LOCAL algorithm importantly both knows all the past arrived nodes and their randomness, and can also consider all the different choices of the adversary in the future, and hence can compute the above conditional probabilities.

At the end of the simulation of $\mathcal{A}$, we have $\Pr[\mathcal{F}|B_1 = b_1, \dots, B_n = b_n] < 1$, and hence the bad event $\mathcal{F}$ does not occur. This implies that the algorithm $\mathcal{A}'$ is always correct. $\square$

**Remark 10.2.** This proof assumes that we have white-box access to the randomized online-LOCAL algorithm and that it uses finitely many random bits. If either of these assumptions does not hold, we can use a more inefficient derandomization along the lines of [30]. Here, we just observe that an online-LOCAL algorithm working against an adaptive adversary implies the existence of a function $f$ that maps all possible input sequences on all possible $n$-node graphs that can be produced by the adversary to a valid output of the problem $\Pi$. The deterministic online-LOCAL algorithm finds such a function $f$ at the beginning of its execution and produces the output according to $f$.
# 11 LCL problems in paths and cycles in randomized online-LOCAL

In this section, we show that the complexity of LCLs in paths and cycles is either $O(1)$ or $\Theta(n)$ in
randomized online-LOCAL (with an oblivious adversary).

**Theorem 11.1.** Let $\Pi$ be an LCL problem on paths and cycles (possibly with inputs). If the locality of $\Pi$ is $T$ in the randomized online-LOCAL model, then its locality is $O(T + \log^* n)$ in the LOCAL model.

This theorem is a simple corollary of the following two lemmas:

**Lemma 11.2.** Let $\Pi$ be an LCL problem on paths and cycles (possibly with inputs), and let $\mathcal{A}$ be a randomized online-LOCAL algorithm solving $\Pi$ with locality $o(n)$. Then there exists a randomized online-LOCAL algorithm $\mathcal{A}'$ solving $\Pi$ with locality $O(1)$.

**Lemma 11.3.** Let $\Pi$ be an LCL problem on paths and cycles (possibly with inputs), and let $\mathcal{A}$ be a randomized online-LOCAL algorithm solving $\Pi$ with locality $O(1)$. Then there exists a LOCAL algorithm $\mathcal{A}'$ solving $\Pi$ with locality $O(\log^* n)$.

By previous results [2], it is known that, in the case of paths and cycles, any (deterministic)
online-LOCAL algorithm with sublinear locality can be sped up to an online-LOCAL algorithm with
constant locality. We show how to extend [2, Lemma 5.5]. We start by constructing a large virtual
graph $P'$ such that, when the original algorithm runs on the virtual graph $P'$, the labeling produced
by the algorithm is locally compatible with the labeling in the original graph $P$.

*Proof of Lemma 11.2.* Let $\Pi$ be an LCL problem in paths or cycles with checking-radius $r$, let $P$ be a path or a cycle with $n$ nodes, and let $\mathcal{A}$ be a randomized online-LOCAL algorithm solving $\Pi$ with locality $T(n) = o(n)$. In the proof of [2, Lemma 5.5], the authors use three phases to speed up (deterministic) online-LOCAL with sublinear locality to only constant locality. We use the same strategy to construct a randomized online-LOCAL algorithm $\mathcal{A}'$ for solving $\Pi$ with constant locality. The phases for constructing randomized online-LOCAL algorithm $\mathcal{A}'$ are as follows:

1. In the first phase, the algorithm deterministically creates an $(\alpha, \alpha)$-ruling set $R$ for the path $P$, mirroring the approach outlined in the proof of [2, Lemma 5.5].

2. In the second phase, the algorithm constructs a larger virtual path $P'$ with $N$ nodes and simulates algorithm $\mathcal{A}$ on $P'$ in the neighborhoods of nodes in $R$. Intuitively this path $P'$ is constructed based on the pumping-lemma-style argument on LCL problems presented by Chang and Pettie [19], and it only relies on (the definition of) problem $\Pi$, not the algorithm $\mathcal{A}$. During this simulation, the algorithm encounters a failure only if $\mathcal{A}$ fails within specific neighborhoods of $P'$. Consequently, the algorithm's success in this phase aligns with the success rate of $\mathcal{A}$, ensuring a high probability of success.

3. The third phase is also as in [2, Lemma 5.5]: The algorithm extends the fixed labels around $R$ to the entire path $P$ by applying brute force for nodes outside the neighborhood of $R$. Note that this extending is feasible because of the way the path $P'$ is created and the pumping-lemma-style argument as discussed in [2].

In the end, we compose these three phases together to obtain the randomized online-LOCAL algorithm $\mathcal{A}'$ for solving $\Pi$ with constant locality. $\square$
*Proof of Lemma 11.3.* This proof closely follows the argument presented in [2, Lemma 5.6]. Let $\Pi$ denote an LCL problem with a constant checking-radius $r$, and suppose $\mathcal{A}$ is a randomized online-LOCAL algorithm solving $\Pi$ with constant locality $T$. Define $\beta = T + r + 1$. As in [2, Lemma 5.6], we consider an input-labeled graph $P$ formed by many copies of all feasible input neighborhoods with a radius of $\beta$. We can depict $P$ as a collection of disjoint path fragments that we later connect to each other and create a long path with. Each of these path fragments has size $2\beta + 1$, so the node in the center of each segment (i.e., the $(\beta + 1)$-th node in the segment) has the same view (up to radius $\beta$) as in the final path. Let $V$ be the set of central nodes within these fragments.

We apply $\mathcal{A}$ to each node within the radius-$r$ neighborhood of the nodes in $V$ following an arbitrary order and then terminate. These nodes have the same view as in the final path because their distance to the endpoints is at most $\beta - r = T + 1$. We iterate the process multiple times, yielding a distribution of output labels around the central nodes. Given that the size of $P$ is constant, there exists an output labeling $L$ of the nodes occurring with probability $p = \Omega(1)$. If needed, we can augment $P$ with (constantly many) additional nodes such that $|P| > 1/p$.

We set this labeling $L$ as the deterministic output for graph $P$ and proceed similarly to the deterministic case by constructing the canonical labeling $f$ from $L$. Then, we use the function $f$ to construct a LOCAL algorithm with $O(\log^* n)$ locality following the same steps as in the proof of [2, Lemma 5.6]. It is important to highlight that it is feasible to fill any gap of sufficient length between parts labeled with the canonical labeling: If the algorithm $\mathcal{A}$ would never produce a valid labeling for this gap, then the algorithm would fail to label $P$ with probability at least $p$ and, since $p \ge 1/|P|$, the algorithm $\mathcal{A}$ would not succeed with high probability. $\square$

## Acknowledgments

We thank anonymous reviewers for their helpful feedback on previous versions of this work. This work was supported in part by the Research Council of Finland, Grant 333837. Xavier Coiteux-Roy is supported by the Swiss National Science Foundation. Francesco d'Amore is supported by MUR FARE 2020 - Project PAReCoDi CUP J43C22000970001. Darya Melnyk is supported by the European Research Council (ERC), grant agreement No. 864228 (AdjustNet), Horizon 2020, 2020-2025. Augusto Modanese and Shreyas Pai are supported by the Helsinki Institute for Information Technology (HIIT). Marc-Olivier Renou acknowledges funding by INRIA through the Action Exploratoire project DEPARTURE, and by the ANR for the JCJC grant LINKS (ANR-23-CE47-0003).

**Errata.** An earlier version of this manuscript (arXiv:2403.01903v1, posted on 2024-03-04) had a mistake: we claimed a result analogous to Theorem 1.5 for *unrooted* trees (which would also have implications on the complexity of the sinkless orientation problem). However, the proof had a missing step, and we do not know if the proof can be fixed.

## References

[1] Jon Aaronson, David Gilat, Michael Keane, and Vincent de Valk. An algebraic construction of a class of one-dependent processes. *The Annals of Probability*, 17(1):128–143, 1989.

[2] Amirreza Akbari, Navid Eslami, Henrik Lievonen, Darya Melnyk, Joona Särkijä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*,