One of the most successful theoretical models in distributed computing is LOCAL, introduced in a seminal work by Linial [SIAM J. Comp. 1992]. Over the years, when studying distributed graph problems in the LOCAL model, researchers made different assumptions on the exact details of this model. For example, sometimes it is assumed that all machines know the exact size of the network, other times machines are assumed to only know a polynomial upper bound on the size of the network, while sometimes no prior knowledge is assumed. Are these small differences irrelevant details or do they actually heavily affect the obtained results? We investigate how robust our current understanding of the LOCAL model truly is, by focusing on one of the most studied classes of problems, called Locally Checkable Labelings (LCLs).

In this work, we study the Lovász local lemma (LLL) problem in the area of distributed quantum computing, which has been the focus of attention of recent advances in quantum computing [STOC’24, STOC’25, STOC’25]. We prove a lower bound of \(2^{\Omega(\log^*n)}\) for the complexity of the distributed LLL in the quantum-LOCAL model. More specifically, we obtain our lower bound already for a very well-studied special case of the LLL, called sinkless orientation, in a stronger model than quantum-LOCAL, called the randomized online-LOCAL model. As a consequence, we obtain the same lower bounds for sinkless orientation and the distributed LLL also in a variety of other models studied across different research communities.

Recent work on distributed graph algorithms [e.g. STOC 2022, ITCS 2022, PODC 2020] has drawn attention to the following open question: are round elimination fixed points a universal technique for proving lower bounds? That is, given a locally checkable problem \(\Pi\) that requires at least \(\Omega(\log n)\) rounds in the deterministic LOCAL model, can we always find a relaxation \(\Pi'\) of \(\Pi\) that is a nontrivial fixed point for the round elimination technique [see STOC 2016, PODC 2019]? If yes, then a key part of distributed computational complexity would be also decidable.

Recent improvements on the deterministic complexities of fundamental graph problems in the LOCAL model of distributed computing have yielded state-of-the-art upper bounds of \(\tilde{O}(\log^{5/3} n)\) rounds for maximal independent set (MIS) and \((\Delta + 1)\)-coloring [Ghaffari, Grunau, FOCS’24], and \(\tilde{O}(\log^{19/9} n)\) rounds for the more restrictive \(\Delta\)-coloring problem [Ghaffari, Kuhn, FOCS’21; Ghaffari, Grunau, FOCS’24; Bourreau, Brandt, Nolin, STOC’25]. In our work, we show that \(\Delta\)-coloring can be solved deterministically in \(\tilde{O}(\log^{5/3} n)\) rounds as well, matching the currently best bound for \((\Delta + 1)\)-coloring.

Understanding the role of randomness when solving locally checkable labeling (LCL) problems in the LOCAL model has been one of the top priorities in the research on distributed graph algorithms in recent years. For LCL problems in bounded-degree graphs, it is known that randomness cannot help more than polynomially, except in one case: if the deterministic complexity of an LCL problem is in Ω(log n) and its randomized complexity is in o(log n), then the randomized complexity is guaranteed to be O(poly(log log n)) and it is even known to be O(log log n) in bounded-degree trees. However, the fundamental question of which problems with a deterministic complexity of Ω(log n) can be solved exponentially faster using randomization still remains wide open. We make a step towards answering this question by studying a simple, but natural class of LCL problems: so-called degree splitting problems. These problems come in two varieties: coloring problems where the edges of a graph have to be colored with 2 colors and orientation problems where each edge needs to be oriented. For an exact classification, it is most natural to consider the Δ-regular case (for Δ = O(1)), where we obtain the following results. - We exactly characterize the complexity of problems where the edges need to be colored with two colors, say red and blue. We show that for every y ∈ {0,… ,Δ-1}, the problem of red-blue coloring the edges such that every node of degree Δ has either y or y+1 red edges has randomized complexity O(log log n) in general graphs of maximum degree Δ. Any other problem, i.e., any problem that does not allow two consecutive red degrees, is already known to have randomized complexity Ω(log n) even in Δ-regular trees. We note that a set of edges F such that every node has either y or y+1 incident edges in F is also known as a {y,y+1}-factor of a graph. - For edge orientations, we show that for any two r₁ and r₂ such that r₁,r₂ ≤ Δ/2 and r₁+r₂ ≥ Δ/2, there are randomized algorithms with round complexities O(log log n) in trees and Õ(log⁴log n) in general graphs to compute an edge orientation such that all nodes have outdegree r₁ ± O(√{ΔlogΔ}) or Δ-r₂ ± O(√{ΔlogΔ}). Further, there exists a constant c > 0 such that for any 0 ≤ r₁+r₂ ≤ Δ/2, the problem of computing an edge orientation in which all outdegrees are either at most r₁-c⋅ √{Δ} or at least Δ-r₂+c⋅√{Δ} has randomized complexity Ω(log n) even in Δ-regular trees. While our results are cleanest to state for the Δ-regular case, all our algorithms naturally generalize to nodes of any degree d < Δ in general graphs of maximum degree Δ. All our algorithms also naturally generalize to the unbounded degree case and they then have a randomized complexity of Õ(Δ) ⋅ log log n (resp. Õ(Δ ⋅log⁴log n) for orienting general graphs).

While obtaining optimal algorithms for the most important problems in the LOCAL model has been one of the central goals in the area of distributed algorithms since its infancy, tight complexity bounds are elusive for many problems even when considering deterministic complexities on trees. We take a step towards remedying this issue by providing a way to relate the complexity of a problem Π on trees to its truly local complexity, which is the (asymptotically) smallest function f such that Π can be solved in O(f(Δ) + log* n) rounds. More specifically, we develop a transformation that takes an algorithm A for Π with a runtime of O(f(Δ) + log* n) rounds as input and transforms it into an O(f(g(n)) +log* n)-round algorithm A′ on trees, where g is the function that satisfies g(n)f(g(n)) = n. If f is the truly local complexity of Π (i.e., if A is asymptotically optimal), then A′ is an asymptotically optimal algorithm on trees, conditioned on a natural assumption on the nature of the worst-case instances of Π.

The last five years of research on distributed graph algorithms have seen huge leaps of progress, both regarding algorithmic improvements and impossibility results: new strong lower bounds have emerged for many central problems and exponential improvements over the state of the art have been achieved for the runtimes of many algorithms. Nevertheless, there are still large gaps between the best known upper and lower bounds for many important problems.

We present the first local problem that shows a super-constant separation between the classical randomized LOCAL model of distributed computing and its quantum counterpart. By prior work, such a separation was known only for an artificial graph problem with an inherently global definition [Le Gall et al. 2019]. We present a problem that we call iterated GHZ, which is defined using only local constraints. Formally, it is a family of locally checkable labeling problems [Naor and Stockmeyer 1995]; in particular, solutions can be verified with a constant-round distributed algorithm. We show that in graphs of maximum degree $Δ$, any classical (deterministic or randomized) LOCAL model algorithm will require $Ω(Δ)$ rounds to solve the iterated GHZ problem, while the problem can be solved in $1$ round in quantum-LOCAL. We use the round elimination technique to prove that the iterated GHZ problem requires $Ω(Δ)$ rounds for classical algorithms. This is the first work that shows that round elimination is indeed able to separate the two models, and this also demonstrates that round elimination cannot be used to prove lower bounds for quantum-LOCAL. To apply round elimination, we introduce a new technique that allows us to discover appropriate problem relaxations in a mechanical way; it turns out that this new technique extends beyond the scope of the iterated GHZ problem and can be used to e.g. reproduce prior results on maximal matchings [FOCS 2019, PODC 2020] in a systematic manner.

Brooks’ theorem states that all connected graphs but odd cycles and cliques can be colored with Δ colors, where Δ is the maximum degree of the graph. Such colorings have been shown to admit non-trivial distributed algorithms [Panconesi and Srinivasan, Combinatorica 1995] and have been studied intensively in the distributed literature. In particular, it is known that any deterministic algorithm computing a Δ-coloring requires Ω(logn) rounds in the LOCAL model [Chang, Kopelowitz, and Pettie, FOCS 2016], and that this lower bound holds already on constant-degree graphs. In contrast, the best upper bound in this setting is given by an O(log2 n)-round deterministic algorithm that can be inferred already from the works of [Awerbuch, Goldberg, Luby, and Plotkin, FOCS 1989] and [Panconesi and Srinivasan, Combinatorica 1995] roughly three decades ago, raising the fundamental question about the true complexity of Δ-coloring in the constant-degree setting. We answer this long-standing question almost completely by providing an almost-optimal deterministic O(logn log* n)-round algorithm for Δ-coloring, matching the lower bound up to a log* n-factor. Similarly, in the randomized LOCAL model, we provide an O(loglogn log* n)-round algorithm, improving over the state-of-the-art upper bound of O(log2 logn) [Ghaffari, Hirvonen, Kuhn, and Maus, Distributed Computing 2021] and almost matching the Ω(loglogn)-round lower bound by [BFHKLRSU, STOC 2016]. Our results make progress on several important open problems and conjectures. One key ingredient for obtaining our results is the introduction of ruling subgraph families as a novel tool for breaking symmetry between substructures of a graph, which we expect to be of independent interest.

Algorithms with advice have received ample attention in the distributed and online settings, and they have recently proven useful also in dynamic settings. In this work we study local computation with advice: the goal is to solve a graph problem Π with a distributed algorithm in T(Δ) communication rounds, for some function T that only depends on the maximum degree Δ of the graph, and the key question is how many bits of advice per node are needed. Some of our results regard Locally Checkable Labeling problems (LCLs), which is an important family of problems that includes various coloring and orientation problems on finite-degree graphs. These are constraint-satisfaction graph problems that can be defined with a finite set of valid input/output-labeled neighborhoods. Our main results are: 1) Any locally checkable labeling problem can be solved with only 1 bit of advice per node in graphs with sub-exponential growth (the number of nodes within radius r is sub-exponential in r; for example, grids are such graphs). Moreover, we can make the set of nodes that carry advice bits arbitrarily sparse. As a corollary, any locally checkable labeling problem admits a locally checkable proof with 1 bit per node in graphs with sub-exponential growth. 2) The assumption of sub-exponential growth is complemented by a conditional lower bound: assuming the Exponential-Time Hypothesis, there are locally checkable labeling problems that cannot be solved in general with any constant number of bits per node. 3) In any graph we can find an almost-balanced orientation (indegrees and outdegrees differ by at most one) with 1 bit of advice per node, and again we can make the advice arbitrarily sparse. As a corollary, we can also compress an arbitrary subset of edges so that a node of degree d stores only d/2 + 2 bits, and we can decompress it locally, in T(Δ) rounds. 4) In any graph of maximum degree Δ, we can find a Δ-coloring (if it exists) with 1 bit of advice per node, and again, we can make the advice arbitrarily sparse. 5) In any 3-colorable graph, we can find a 3-coloring with 1 bit of advice per node. As a corollary, in bounded-degree graphs there is a locally checkable proof that certifies 3-colorability with 1 bit of advice per node, while prior work shows that this is not possible with a proof labeling scheme (PLS), which is a more restricted setting where the verifier can only see up to distance 1. Our work shows that for many problems the key threshold is not whether we can achieve 1 bit of advice per node, but whether we can make the advice arbitrarily sparse. To formalize this idea, we develop a general framework of composable schemas that enables us to build algorithms for local computation with advice in a modular fashion: once we have (1) a schema for solving Π₁ and (2) a schema for solving Π₂ assuming an oracle for Π₁, we can also compose them and obtain (3) a schema that solves Π₂ without the oracle. It turns out that many natural problems admit composable schemas, all of them can be solved with only 1 bit of advice, and we can make the advice arbitrarily sparse.

In the past few years, a successful line of research has led to lower bounds for several fundamental local graph problems in the distributed setting. These results were obtained via a technique called round elimination. On a high level, the round elimination technique can be seen as a recursive application of a function that takes as input a problem Π and outputs a problem Π' that is one round easier than Π. Applying this function recursively to concrete problems of interest can be highly nontrivial, which is one of the reasons that has made the technique difficult to approach. The contribution of our paper is threefold. Firstly, we develop a new and fully automatic method for finding so-called fixed point relaxations under round elimination. The detection of a non-0-round solvable fixed point relaxation of a problem Π immediately implies lower bounds of Ω(log_Δ n) and Ω(log_Δ log n) rounds for deterministic and randomized algorithms for Π, respectively. Secondly, we show that this automatic method is indeed useful, by obtaining lower bounds for defective coloring problems. More precisely, as an application of our procedure, we show that the problem of coloring the nodes of a graph with 3 colors and defect at most (Δ - 3)/2 requires Ω(log_Δ n) rounds for deterministic algorithms and Ω(log_Δ log n) rounds for randomized ones. Additionally, we provide a simplified proof for an existing defective coloring lower bound. We note that lower bounds for coloring problems are notoriously challenging to obtain, both in general, and via the round elimination technique. {Both the first and (indirectly) the second contribution build on our third contribution: a new method to compute the one-round easier problem Π' in the round elimination framework. This method heavily simplifies the usage of the round elimination technique, and in fact it has been successfully exploited in a recent work in order to prove quantum advantage in the distributed setting [STOC '25].}

Abstract Locally Checkable Labeling () problems are graph problems in which a solution is correct if it satisfies some given constraints in the local neighborhood of each node. Example problems in this class include maximal matching, maximal independent set, and colorings. A successful line of research has been studying the complexities of s on paths/cycles, trees, and general graphs, providing many interesting results for the model of distributed computing. In this work, we initiate the study of problems in the low-space Massively Parallel Computation () model. In particular, on forests, we provide a method that, given the complexity of an problem in the model, automatically provides an exponentially faster algorithm for the low-space setting that uses optimal global memory, that is, truly linear. While restricting to forests may seem to weaken the results, we emphasize that all known (conditional) lower bounds for the setting are obtained through lower bounds for problems in the distributed setting in tree-like networks (either trees or high-girth graphs), and hence the problems that we study are challenging already on trees. Moreover, our algorithms use optimal global memory, i.e., memory linear in the number of edges of the graph. In contrast, most of the state-of-the-art algorithms use more than linear global memory. Further, they typically start with a dense graph, sparsify it, and then solve the problem on the residual graph, exploiting the relative increase in global memory. On forests this is not possible, hence using optimal memory requires new solutions.

In this work we study local computation with advice: the goal is to solve a graph problem Π with a distributed algorithm in f (Δ) communication rounds, for some function f that only depends on the maximum degree Δ of the graph, and the key question is how many bits of advice per node are needed. Our main results are:

The node-averaged complexity of a problem captures the number of rounds nodes of a graph have to spend on average to solve the problem in the LOCAL model. A challenging line of research with regards to this new complexity measure is to understand the complexity landscape of locally checkable labelings (LCLs) on families of bounded-degree graphs. Particularly interesting in this context is the family of bounded-degree trees as there, for the worst-case complexity, we know a complete characterization of the possible complexities and structures of LCL problems. A first step for the node-averaged complexity case has been achieved recently [DISC '23], where the authors in particular showed that in bounded-degree trees, there is a large complexity gap: There are no LCL problems with a deterministic node-averaged complexity between ω(log* n) and no(1). For randomized algorithms, they even showed that the node-averaged complexity is either O(1) or nΩ(1). In this work we fill in the remaining gaps and give a complete description of the node-averaged complexity landscape of LCLs on bounded-degree trees. Our contributions are threefold.

In this work, we study the complexity of fundamental distributed graph problems in the recently popular setting where information about the input graph is available to the nodes before the start of the computation. We focus on the most common such setting, known as the Supported LOCAL model, where the input graph---on which the studied graph problem has to be solved---is guaranteed to be a subgraph of the underlying communication network.

We investigate the distributed complexity of maximal matching and maximal independent set (MIS) in hypergraphs in the LOCAL model. A maximal matching of a hypergraph H = (VH, EH) is a maximal disjoint set M ⊆ Eh of hyperedges and an MIS S ⊆ VH is a maximal set of nodes such that no hyperedge is fully contained in S. Both problems can be solved by a simple sequential greedy algorithm, which can be implemented naïvely in O (Δr + log* n) rounds, where Δ is the maximum degree, r is the rank, and n is the number of nodes of the hypergraph. We show that for maximal matching, this naive algorithm is optimal in the following sense. Any deterministic algorithm for solving the problem requires Ω(min {Δr,logΔr n}) rounds, and any randomized one requires Ω(min {Δr, logΔr log n}) rounds. Hence, for any algorithm with a complexity of the form O(f (Δ,r) + g(n)), we have f (Δ,r) ∈ Ω(Δr) if g(n) is not too large, and in particular if g(n) = log* n (which is the optimal asymptotic dependency on n due to Linial's lower bound [FOCS'87]). Our lower bound proof is based on the round elimination framework, and its structure is inspired by a new round elimination fixed point that we give for the Δ-vertex coloring problem in hypergraphs, where nodes need to be colored such that there are no monochromatic hyperedges. For the MIS problem on hypergraphs, we show that for Δ ≪ r, there are significant improvements over the naive O(Δr + log* n)-round algorithm. We give two deterministic algorithms for the problem. We show that a hypergraph MIS can be computed in O(Δ2 · log r + Δ · log r · log* r + log* n) rounds. We further show that at the cost of a much worse dependency on Δ, the dependency on r can be removed almost entirely, by giving an algorithm with round complexity ΔO(Δ) · log* r + 0(log* n).

Abstract Consider any locally checkable labeling problem $$\Pi $$ Π in rooted regular trees: there is a finite set of labels $$\Sigma $$ Σ , and for each label $$x \in \Sigma $$ x ∈ Σ we specify what are permitted label combinations of the children for an internal node of label x (the leaf nodes are unconstrained). This formalism is expressive enough to capture many classic problems studied in distributed computing, including vertex coloring, edge coloring, and maximal independent set. We show that the distributed computational complexity of any such problem $$\Pi $$ Π falls in one of the following classes: it is O(1), $$\Theta (\log ^* n)$$ Θ ( log ∗ n ) , $$\Theta (\log n)$$ Θ ( log n ) , or $$n^{\Theta (1)}$$ n Θ ( 1 ) rounds in trees with n nodes (and all of these classes are nonempty). We show that the complexity of any given problem is the same in all four standard models of distributed graph algorithms: deterministic $$\mathsf {LOCAL}$$ LOCAL , randomized $$\mathsf {LOCAL}$$ LOCAL , deterministic $$\mathsf {CONGEST}$$ CONGEST , and randomized $$\mathsf {CONGEST}$$ CONGEST model. In particular, we show that randomness does not help in this setting, and the complexity class $$\Theta (\log \log n)$$ Θ ( log log n ) does not exist (while it does exist in the broader setting of general trees). We also show how to systematically determine the complexity class of any such problem $$\Pi $$ Π , i.e., whether $$\Pi $$ Π takes O(1), $$\Theta (\log ^* n)$$ Θ ( log ∗ n ) , $$\Theta (\log n)$$ Θ ( log n ) , or $$n^{\Theta (1)}$$ n Θ ( 1 ) rounds. While the algorithm may take exponential time in the size of the description of $$\Pi $$ Π , it is nevertheless practical: we provide a freely available implementation of the classifier algorithm, and it is fast enough to classify many problems of interest.

We study connections between three different fields: distributed local algorithms, finitary factors of iid processes, and descriptive combinatorics. We focus on two central questions: Can we apply techniques from one of the areas to obtain results in another? Can we show that complexity classes coming from different areas contain precisely the same problems? We give an affirmative answer to both questions in the context of local problems on regular trees: 1) We extend the Borel determinacy technique of Marks [Marks - J. Am. Math. Soc. 2016] coming from descriptive combinatorics and adapt it to the area of distributed computing, thereby obtaining a more generally applicable lower bound technique in descriptive combinatorics and an entirely new lower bound technique for distributed algorithms. Using our new technique, we prove deterministic distributed Ω(log n)-round lower bounds for problems from a natural class of homomorphism problems. Interestingly, these lower bounds seem beyond the current reach of the powerful round elimination technique [Brandt - PODC 2019] responsible for all substantial locality lower bounds of the last years. Our key technical ingredient is a novel ID graph technique that we expect to be of independent interest; in fact, it has already played an important role in a new lower bound for the Lovász local lemma in the Local Computation Algorithms model from sequential computing [Brandt, Grunau, Rozhoň - PODC 2021]. 2) We prove that a local problem admits a Baire measurable coloring if and only if it admits a local algorithm with local complexity O(log n), extending the classification of Baire measurable colorings of Bernshteyn [Bernshteyn - personal communication]. A key ingredient of the proof is a new and simple characterization of local problems that can be solved in O(log n) rounds. We complement this result by showing separations between complexity classes from distributed computing, finitary factors, and descriptive combinatorics. Most notably, the class of problems that allow a distributed algorithm with sublogarithmic randomized local complexity is incomparable with the class of problems with a Borel solution. We hope that our treatment will help to view all three perspectives as part of a common theory of locality, in which we follow the insightful paper of [Bernshteyn - arXiv 2004.04905].

We provide new deterministic algorithms for the edge coloring problem, which is one of the classic and highly studied distributed local symmetry breaking problems. As our main result, we show that a (2Δ - 1)-edge coloring can be computed in time poly log Δ + O(log* n) in the LOCAL model. This improves a result of Balliu, Kuhn, and Olivetti [PODC '20], who gave an algorithm with a quasi-polylogarithmic dependency on Δ. We further show that in the CONGEST model, an (8 + ε)Δ-edge coloring can be computed in poly log Δ + O(log* n) rounds. The best previous O(Δ)-edge coloring algorithm that can be implemented in the CONGEST model is by Barenboim and Elkin [PODC '11] and it computes a 2O(1/ε)Δ- edge coloring in time O(Δε + log* n) for any ε ∈ (0, 1].

We study the local complexity landscape of locally checkable labeling (LCL) problems on constant-degree graphs with a focus on complexities below log* n. Our contribution is threefold: (1) Our main contribution is that we complete the classification of the complexity landscape of LCL problems on trees in the LOCAL model, by proving that every LCL problem with local complexity o (log* n) has actually complexityO(1). This result improves upon the previous speedup result from o (log log* n) to O(1) by [Chang, Pettie, FOCS 2017].(2) In the related LCA and VOLUME models [Alon, Rubinfeld, Vardi, Xie, SODA 2012, Rubinfeld, Tamir, Vardi, Xie, 2011, Rosenbaum, Suomela, PODC 2020],we prove the same speedup from o (log* n) to O(1) for all constant-degree graphs.

We prove several new tight or near-tight distributed lower bounds for classic symmetry breaking problems in graphs. As a basic tool, we first provide a new insightful proof that any deterministic distributed algorithm that computes a Δ-coloring on Δ-regular trees requires Ω(logΔn) rounds and any randomized such algorithm requires Ω(logΔlogn) rounds. We prove this by showing that a natural relaxation of the Δ-coloring problem is a fixed point in the round elimination framework.

We give practical, efficient algorithms that automatically determine the asymptotic distributed round complexity of a given locally checkable graph problem in the $[Θ(\log n), Θ(n)]$ region, in two settings. We present one algorithm for unrooted regular trees and another algorithm for rooted regular trees. The algorithms take the description of a locally checkable labeling problem as input, and the running time is polynomial in the size of the problem description. The algorithms decide if the problem is solvable in $O(\log n)$ rounds. If not, it is known that the complexity has to be $Θ(n^{1/k})$ for some $k = 1, 2, \dotsc$, and in this case the algorithms also output the right value of the exponent $k$. In rooted trees in the $O(\log n)$ case we can then further determine the exact complexity class by using algorithms from prior work; for unrooted trees the more fine-grained classification in the $O(\log n)$ region remains an open question.

Locally Checkable Labeling (LCL) problems are graph problems in which a solution is correct if it satisfies some given constraints in the local neighborhood of each node. Example problems in this class include maximal matching, maximal independent set, and coloring problems. A successful line of research has been studying the complexities of LCL problems on paths/cycles, trees, and general graphs, providing many interesting results for the LOCAL model of distributed computing. In this work, we initiate the study of LCL problems in the low-space Massively Parallel Computation (MPC) model. In particular, on forests, we provide a method that, given the complexity of an LCL problem in the LOCAL model, automatically provides an exponentially faster algorithm for the low-space MPC setting that uses optimal global memory, that is, truly linear. While restricting to forests may seem to weaken the result, we emphasize that all known (conditional) lower bounds for the MPC setting are obtained by lifting lower bounds obtained in the distributed setting in tree-like networks (either forests or high girth graphs), and hence the problems that we study are challenging already on forests. Moreover, the most important technical feature of our algorithms is that they use optimal global memory, that is, memory linear in the number of edges of the graph. In contrast, most of the state-of-the-art algorithms use more than linear global memory. Further, they typically start with a dense graph, sparsify it, and then solve the problem on the residual graph, exploiting the relative increase in global memory. On forests, this is not possible, because the given graph is already as sparse as it can be, and using optimal memory requires new solutions.

The Local Computation Algorithm (LCA) model is a popular model in the field of sublinear-time algorithms that measures the complexity of an algorithm by the number of probes the algorithm makes in the neighborhood of one node to determine that node's output. In this paper we show that the randomized LCA complexity of the Lovász Local Lemma (LLL) on constant degree graphs is Θ(log n). The lower bound follows by proving an Ω(log n) lower bound for the Sinkless Orientation problem introduced in [Brandt et al. STOC 2016]. This answers a question of [Rosenbaum, Suomela PODC 2020]. Additionally, we show that every randomized LCA algorithm for a locally checkable problem with a probe complexity of o(√log n ) can be turned into a deterministic LCA algorithm with a probe complexity of O(log^* n). This improves exponentially upon the currently best known speed-up result from o(log log n) to O(log^* n) implied by the result of [Chang, Pettie FOCS 2017] in the LOCAL model. Finally, we show that for every fixed constant c ≥ 2, the deterministic VOLUME complexity of c-coloring a bounded degree tree is Θ(n), where the VOLUME model is a close relative of the LCA model that was recently introduced by [Rosenbaum, Suomela PODC 2020].

Recently, Balliu, Brandt, and Olivetti [FOCS '20] showed the first ω(log n) lower bound for the maximal independent set (MIS) problem in trees. In this work we prove lower bounds for a much more relaxed family of distributed symmetry breaking problems. As a by-product, we obtain improved lower bounds for the distributed MIS problem in trees.

Consider any locally checkable labeling problem Π in rooted regular trees: there is a finite set of labels Σ, and for each label χ x Σ we specify what are permitted label combinations of the children for an internal node of label x (the leaf nodes are unconstrained). This formalism is expressive enough to capture many classic problems studied in distributed computing, including vertex coloring, edge coloring, and maximal independent set.

We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an efficient distributed algorithm for stable orientations and more generally for locally optimal semi-matchings. The prior work by Czygrinow et al. (DISC 2012) finds a stable orientation in O(Δ^5) rounds in graphs of maximum degree Δ, while we improve it to O(Δ^4) and also prove a lower bound of Ω(Δ). For the more general problem of locally optimal semi-matchings, the prior upper bound is O(S^5) and our new algorithm runs in O(C · S^4) rounds, which is an improvement for C = o(S); here C and S are the maximum degrees of customers and servers, respectively.

In this work, we develop the low-space Massively Parallel Computation (MPC) complexity landscape for a family of fundamental graph problems on trees. We present a general method that solves most locally checkable labeling (LCL) problems exponentially faster in the low-space MPC model than in the LOCAL message passing model. In particular, we show that all solvable LCL problems on trees can be solved in $O(\log n)$ time (high-complexity regime) and that all LCL problems on trees with deterministic complexity $n^{o(1)}$ in the LOCAL model can be solved in $O(\log \log n)$ time (mid-complexity regime). We observe that obtaining a greater speed-up than from $n^{o(1)}$ to $Θ(\log \log n)$ is conditionally impossible, since the problem of 3-coloring trees, which is a LCL problem with LOCAL time complexity $n^{o(1)}$, has a conditional MPC lower bound of $Ω(\log \log n)$ [Linial, FOCS'87; Ghaffari, Kuhn and Uitto, FOCS'19]. We emphasize that we solve LCL problems on constant-degree trees, and that our algorithms are deterministic, component-stable, and work in the low-space MPC model, where local memory is $O(n^δ)$ for $δ\in (0,1)$ and global memory is $O(m)$. For the high-complexity regime, there are two key ingredients. One is a novel $O(\log n)$-time tree rooting algorithm, which may be of independent interest. The other is a novel pointer-chain technique and analysis that allows us to solve any solvable LCL problem on trees in $O(\log n)$ time. For the mid-complexity regime, we adapt the approach by Chang and Pettie [FOCS'17], who gave a canonical LOCAL algorithm for solving LCL problems on trees.

Abstract The landscape of the distributed time complexity is nowadays well-understood for subpolynomial complexities. When we look at deterministic algorithms in the $$\mathsf {LOCAL}$$ LOCAL model and locally checkable problems ( $$\mathsf {LCL}$$ LCL s) in bounded-degree graphs, the following picture emerges: There are lots of problems with time complexities of $$\varTheta (\log ^* n)$$ Θ ( log ∗ n ) or $$\varTheta (\log n)$$ Θ ( log n ) . It is not possible to have a problem with complexity between $$\omega (\log ^* n)$$ ω ( log ∗ n ) and $$o(\log n)$$ o ( log n ) . In general graphs, we can construct $$\mathsf {LCL}$$ LCL problems with infinitely many complexities between $$\omega (\log n)$$ ω ( log n ) and $$n^{o(1)}$$ n o ( 1 ) . In trees, problems with such complexities do not exist. However, the high end of the complexity spectrum was left open by prior work. In general graphs there are $$\mathsf {LCL}$$ LCL problems with complexities of the form $$\varTheta (n^\alpha )$$ Θ ( n α ) for any rational $$0 < \alpha \le 1/2$$ 0 < α ≤ 1 / 2 , while for trees only complexities of the form $$\varTheta (n^{1/k})$$ Θ ( n 1 / k ) are known. No $$\mathsf {LCL}$$ LCL problem with complexity between $$\omega (\sqrt{n})$$ ω ( n ) and o(n) is known, and neither are there results that would show that such problems do not exist. We show that: In general graphs, we can construct $$\mathsf {LCL}$$ LCL problems with infinitely many complexities between $$\omega (\sqrt{n})$$ ω ( n ) and o(n). In trees, problems with such complexities do not exist. Put otherwise, we show that any $$\mathsf {LCL}$$ LCL

There are distributed graph algorithms for finding maximal matchings and maximal independent sets in O ( Δ + log * n ) communication rounds; here, n is the number of nodes and Δ is the maximum degree. The lower bound by Linial (1987, 1992) shows that the dependency on n is optimal: These problems cannot be solved in o (log * n ) rounds even if Δ = 2. However, the dependency on Δ is a long-standing open question, and there is currently an exponential gap between the upper and lower bounds. We prove that the upper bounds are tight. We show that any algorithm that finds a maximal matching or maximal independent set with probability at least 1-1/ n requires Ω (min { Δ , log log n / log log log n }) rounds in the LOCAL model of distributed computing. As a corollary, it follows that any deterministic algorithm that finds a maximal matching or maximal independent set requires Ω (min { Δ , log n / log log n }) rounds; this is an improvement over prior lower bounds also as a function of n .

Given a graph G=(V, E), an ( α,β) -ruling set is a subset S ⊆ V such that the distance between any two vertices in S is at least α, and the distance between any vertex in V and the closest vertex in S is at most β. We present lower bounds for distributedly computing ruling sets. More precisely, for the problem of computing a ( 2, β) - ruling set (and hence also any ( α,β) -ruling set with ) in the LOCAL model of distributed computing, we show the following, where n denotes the number of vertices, Δ the maximum degree, and c is some universal constant independent of n and Δ. · Any deterministic algorithm requires Ω(min{[(logΔ)/(β log log Δ)], logΔn}) rounds, for all β ≤ c·min{√{[(log Δ)/(log log Δ)]}, logΔn}. By optimizing Δ, this implies a deterministic lower bound of Ω(√{[log n/(β log log n)]}) for all β ≤ c3√{[log n/log log n]}. ·Any randomized algorithm requires Ω(min{[(log Δ)/(β log log Δ)], log log n}) rounds, for all β ≤ c·min{√{[(log Δ)/(log log Δ)]}, log log n}. By optimizing Δ, this implies a randomized lower bound of Ω(√{[log log n/(βlog log log n)]}) for all β ≤ c3√{[log log n/log log log n]}. For , this improves on the previously best lower bound of Ω(log*n) rounds that follows from the 30-year-old bounds of Linial [FOCS'87] and Naor [J.Disc.Math.'91] (resp. Ω(1) rounds if β ∈ ω(log*n)). For β = 1, i.e., for the problem of computing a maximal independent set (which is nothing else than a (2, 1)-ruling set), our results improve on the previously best lower bound of Ω(log*n) on trees, as our bounds already hold on trees.

Recently, Brandt, Maus and Uitto [PODC'19] showed that, in a restricted setting, the dependency of the complexity of the distributed Lovász Local Lemma (LLL) on the chosen LLL criterion exhibits a sharp threshold phenomenon: They proved that, under the LLL criterion p2d < 1, if each random variable affects at most 3 events, the deterministic complexity of the LLL in the LOCAL model is O(d2 + log* n). In stark contrast, under the criterion p2d ≤ 1, there is a randomized lower bound of Ω(log log n) by Brandt et al. [STOC'16] and a deterministic lower bound of Ω(log n) by Chang, Kopelowitz and Pettie [FOCS'16]. Brandt, Maus and Uitto conjectured that the same behavior holds for the unrestricted setting where each random variable affects arbitrarily many events.

In a recent breakthrough result, Balliu et al. [FOCS'19] proved a deterministic Ω(min(Δ, log n/ log log n))-round and a randomized Ω(min(Δ, log log n/ log log log n))-round lower bound for the complexity of the bipartite maximal matching problem on n-node graphs in the LOCAL model of distributed computing. Both lower bounds are asymptotically tight as a function of the maximum degree Δ.

We present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees in the usual LOCAL model of distributed computing. These are locally checkable problems that can be encoded with an alphabet of size two in the edge labeling formalism. Examples of binary labeling problems include sinkless orientation, sinkless and sourceless orientation, 2-vertex coloring, and perfect matching. We show that the complexity of any such problem is in one of the following classes: O(1), Θ(log n), Θ(n), or unsolvable. Furthermore, given the description of any binary labeling problem, we can easily determine in which of the four classes it is and what is an asymptotically optimal algorithm for solving it.

Locally checkable labeling problems (LCLs) are distributed graph problems in which a solution is globally feasible if it is locally feasible in all constant-radius neighborhoods. Vertex colorings, maximal independent sets, and maximal matchings are examples of LCLs.

We study the problem of exploring an oriented grid with autonomous agents governed by finite automata. In the case of a 2-dimensional grid, the question how many agents are required to explore the grid, or equivalently, find a hidden treasure in the grid, is fully understood in both the synchronous and the semi-synchronous setting. For higher dimensions, Dobrev, Narayanan, Opatrny, and Pankratov [ICALP'19] showed very recently that, surprisingly, a (small) constant number of agents suffices to find the treasure, independent of the number of dimensions, thereby disproving a conjecture by Cohen, Emek, Louidor, and Uitto [SODA'17]. Dobrev et al. left as an open question whether their bounds on the number of agents can be improved. We answer this question in the affirmative for deterministic finite automata: we show that 3 synchronous and 4 semi-synchronous agents suffice to explore an $n$-dimensional grid for any constant $n$. The bounds are optimal and notably, the matching lower bounds already hold in the 2-dimensional case. Our techniques can also be used to make progress on other open questions asked by Dobrev et al.: we prove that 4 synchronous and 5 semi-synchronous agents suffice for polynomial-time exploration, and we show that, under a natural assumption, 3 synchronous and 4 semi-synchronous agents suffice to explore unoriented grids of arbitrary dimension (which, again, is tight).

We present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees. These are locally checkable problems that can be encoded with an alphabet of size two in the edge labeling formalism. Examples of binary labeling problems include sinkless orientation, sinkless and sourceless orientation, 2-vertex coloring, perfect matching, and the task of coloring edges red and blue such that all nodes are incident to at least one red and at least one blue edge. More generally, we can encode e.g. any cardinality constraints on indegrees and outdegrees. We study the deterministic time complexity of solving a given binary labeling problem in trees, in the usual LOCAL model of distributed computing. We show that the complexity of any such problem is in one of the following classes: $O(1)$, $Θ(\log n)$, $Θ(n)$, or unsolvable. In particular, a problem that can be represented in the binary labeling formalism cannot have time complexity $Θ(\log^* n)$, and hence we know that e.g. any encoding of maximal matchings has to use at least three labels (which is tight). Furthermore, given the description of any binary labeling problem, we can easily determine in which of the four classes it is and what is an asymptotically optimal algorithm for solving it. Hence the distributed time complexity of binary labeling problems is decidable, not only in principle, but also in practice: there is a simple and efficient algorithm that takes the description of a binary labeling problem and outputs its distributed time complexity.

Abstract Recently, there has been a growing interest in grid exploration by agents with limited capabilities. We show that the grid cannot be explored by three semi-synchronous finite automata, answering an open question by Emek et al. (Theor Comput Sci 608:255–267, 2015) in the negative. In the setting we consider, time is divided into discrete steps, where in each step, an adversarially selected subset of the agents executes one look–compute–move cycle. The agents operate according to a shared finite automaton, where every agent is allowed to have a distinct initial state. The only means of communication is to sense the states of the agents sharing the same grid cell. The agents are equipped with a global compass and whenever an agent moves, the destination cell of the movement is chosen by the agent’s automaton from the set of neighboring grid cells. In contrast to the four agent protocol by Emek et al., we show that three agents do not suffice for grid exploration.

There are distributed graph algorithms for finding maximal matchings and maximal independent sets in O(Δ + log^* n) communication rounds; here n is the number of nodes and Δ is the maximum degree. The lower bound by Linial (1987, 1992) shows that the dependency on n is optimal: these problems cannot be solved in o(log^* n) rounds even if Δ = 2. However, the dependency on Δ is a long-standing open question, and there is currently an exponential gap between the upper and lower bounds. We prove that the upper bounds are tight. We show that maximal matchings and maximal independent sets cannot be found in o(Δ + log log n / log log log n) rounds with any randomized algorithm in the LOCAL model of distributed computing. As a corollary, it follows that there is no deterministic algorithm for maximal matchings or maximal independent sets that runs in o(Δ + log n / log log n) rounds; this is an improvement over prior lower bounds also as a function of n.

Consider a computer network that consists of a path with n nodes. The nodes are labeled with inputs from a constant-sized set, and the task is to find output labels from a constant-sized set subject to some local constraints---more formally, we have an LCL (locally checkable labeling) problem. How many communication rounds are needed (in the standard LOCAL model of computing) to solve this problem?

The Massively Parallel Computation (MPC) model serves as a common abstraction of many modern large-scale parallel computation frameworks and has recently gained a lot of importance, especially in the context of classic graph problems. In this work, we mainly consider maximal matching and maximal independent set problems in the MPC model.

Recently, Brandt et al.\ [STOC'16] proved a lower bound for the distributed Lovász Local Lemma, which has been conjectured to be tight for sufficiently relaxed LLL criteria by Chang and Pettie [FOCS'17]. At the heart of their result lies a speedup technique that, for graphs of girth at least 2t+2, transforms any t-round algorithm for one specific LLL problem into a (t-1)-round algorithm for the same problem. We substantially improve on this technique by showing that such a speedup exists for any locally checkable problem ¶i, with the difference that the problem ¶i_1 the inferred (t-1)-round algorithm solves is not (necessarily) the same problem as ¶i. Our speedup is automatic in the sense that there is a fixed procedure that transforms a description for ¶i into a description for ¶i_1 and reversible in the sense that any (t-1)-round algorithm for ¶i_1 can be transformed into a t-round algorithm for ¶i. In particular, for any locally checkable problem ¶i with exact deterministic time complexity T(n, Δ) łeq t on graphs with n nodes, maximum node degree Δ, and girth at least 2t+2, there is a sequence of problems ¶i_1, ¶i_2, \dots with time complexities T(n, Δ)-1, T(n, Δ)-2, \dots, that can be inferred from ¶i. As a first application of our generalized speedup, we solve a long-standing open problem of Naor and Stockmeyer [STOC'93]: we show that weak 2-coloring in odd-degree graphs cannot be solved in o(łog^* Δ) rounds, thereby providing a matching lower bound to their upper bound.

The Lovász Local Lemma (LLL) says that, given a set of bad events that depend on the values of some random variables and where each event happens with probability at most p and depends on at most d other events, there is an assignment of the variables that avoids all bad events if the LLL criterion ep(d+1)<1 is satisfied. Nowadays, in the area of distributed graph algorithms it has also become a powerful framework for developing---mostly randomized---algorithms. A classic result by Moser and Tardos yields an O(log^2 n) algorithm for the distributed Lovász Local Lemma [JACM'10] if ep(d + 1) < 1 is satisfied. Given a stronger criterion, i.e., demanding a smaller error probability, it is conceivable that we can find better algorithms. Indeed, for example Chung, Pettie and Su [PODC'14] gave an O(log_epd^2 n) algorithm under the epd^2 < 1 criterion. Going further, Ghaffari, Harris and Kuhn introduced an 2^O(√log log n ) time algorithm given d^8 p = O(1) [FOCS'18]. On the negative side, Brandt et al.\ and Chang et al.\ showed that we cannot go below Ω(log log n) (randomized) [STOC'16] and Ω(log n) (deterministic) [FOCS'16], respectively, under the criterion pleq 2^-d . Furthermore, there is a lower bound of Ω(log^* n) that holds for any criterion. In this paper, we study the dependency of the distributed complexity of the LLL problem on the chosen LLL criterion. We show that for the fundamental case of each random variable of the considered LLL instance being associated with an edge of the input graph, that is, each random variable influences at most two events, a sharp threshold phenomenon occurs at p = 2^-d : we provide a simple deterministic (!) algorithm that matches the Ω(log^* n) lower bound in bounded degree graphs, if p < 2^-d , whereas for p \geq 2^-d , the Ωmega(log log n) randomized and the Ω(log n) deterministic lower bounds hold. In many applications variables affect more than two events; our main contribution is to extend our algorithm to the case where random variables influence at most three different bad events. We show that, surprisingly, the sharp threshold occurs at the exact same spot, providing evidence for our conjecture that this phenomenon always occurs at p = 2^-d , independent of the number r of events that are affected by a variable. Almost all steps of the proof framework we provide for the case r=3 extend directly to the case of arbitrary r; consequently, our approach serves as a step towards characterizing the complexity of the LLL under different exponential criteria.

Cops and Robbers is a classic pursuit-evasion game played between a group of g cops and one robber on an undirected N-vertex graph G. We prove that the complexity of deciding the winner in the game under optimal play requires Omega (N^{g-o(1)}) time on instances with O(N log^2 N) edges, conditioned on the Strong Exponential Time Hypothesis. Moreover, the problem of calculating the minimum number of cops needed to win the game is 2^{Omega (sqrt{N})}, conditioned on the weaker Exponential Time Hypothesis. Our conditional lower bound comes very close to a conditional upper bound: if Meyniel's conjecture holds then the cop number can be decided in 2^{O(sqrt{N}log N)} time. In recent years, the Strong Exponential Time Hypothesis has been used to obtain many lower bounds on classic combinatorial problems, such as graph diameter, LCS, EDIT-DISTANCE, and REGEXP matching. To our knowledge, these are the first conditional (S)ETH-hard lower bounds on a strategic game.

Recently, there has been a growing interest in grid exploration by agents with limited capabilities. We show that the grid cannot be explored by three semi-synchronous finite automata, answering an open question by Emek et al. [TCS'15] in the negative. In the setting we consider, time is divided into discrete steps, where in each step, an adversarially selected subset of the agents executes one look-compute-move cycle. The agents operate according to a shared finite automaton, where every agent is allowed to have a distinct initial state. The only means of communication is to sense the states of the agents sharing the same grid cell. The agents are equipped with a global compass and whenever an agent moves, the destination cell of the movement is chosen by the agent's automaton from the set of neighboring grid cells. In contrast to the four agent protocol by Emek et al., we show that three agents do not suffice for grid exploration.

For the game of Cops and Robbers, it is known that in 1-cop-win graphs, the cop can capture the robber in O(n) time, and that there exist graphs in which this capture time is tight. When k >= 2, a simple counting argument shows that in k-cop-win graphs, the capture time is at most O(n^{k + 1}), however, no non-trivial lower bounds were previously known; indeed, in their 2011 book, Bonato and Nowakowski ask whether this upper bound can be improved. In this paper, the question of Bonato and Nowakowski is answered on the negative, proving that the O(n^{k + 1}) bound is asymptotically tight for any constant k >= 2. This yields a surprising gap in the capture time complexities between the 1-cop and the 2-cop cases.

LCLs or locally checkable labelling problems (e.g. maximal independent set, maximal matching, and vertex colouring) in the LOCAL model of computation are very well-understood in cycles (toroidal 1-dimensional grids): every problem has a complexity of O(1), Θ(log* n), or Θ(n), and the design of optimal algorithms can be fully automated. This work develops the complexity theory of LCL problems for toroidal 2-dimensional grids. The complexity classes are the same as in the 1-dimensional case: O(1), Θ(log* n), and Θ(n). However, given an LCL problem it is undecidable whether its complexity is Θ(log* n) or Θ(n) in 2-dimensional grids.

We study consistent migration of flows, with special focus on software defined networks. Given a current and a desired network flow configuration, we give the first polynomial-time algorithm to decide if a congestion-free migration is possible. However, if all flows must be integer or are unsplittable, this is NP-hard to decide. A similar problem is providing increased bandwidth to an application, while keeping all other flows in the network, but possibly migrating them consistently to other paths. We show that the maximum increase can be approximated arbitrarily well in polynomial time. Current methods as RSVP-TE consider unsplittable flows and remove flows of lesser importance in order to increase bandwidth for an application: We prove that deciding what flows need to be removed is an NP-hard optimization problem with no PTAS possible unless P = NP.

We show that any randomised Monte Carlo distributed algorithm for the Lovász local lemma requires Omega(log log n) communication rounds, assuming that it finds a correct assignment with high probability. Our result holds even in the special case of d = O(1), where d is the maximum degree of the dependency graph. By prior work, there are distributed algorithms for the Lovász local lemma with a running time of O(log n) rounds in bounded-degree graphs, and the best lower bound before our work was Omega(log* n) rounds [Chung et al. 2014].