We present a complete classification of the distributed computational complexity of local optimization problems in directed cycles for both the deterministic and the randomized LOCAL model. We show that for any local optimization problem Π (that can be of the form min-sum, max-sum, min-max, or max-min, for any local cost or utility function over some finite alphabet), and for any constant approximation ratio α, the task of finding an α-approximation of Π in directed cycles has one of the following complexities: 1) O(1) rounds in deterministic LOCAL, O(1) rounds in randomized LOCAL, 2) Θ(log^* n) rounds in deterministic LOCAL, O(1) rounds in randomized LOCAL, 3) Θ(log^* n) rounds in deterministic LOCAL, Θ(log^* n) rounds in randomized LOCAL, 4) Θ(n) rounds in deterministic LOCAL, Θ(n) rounds in randomized LOCAL. Moreover, for any given Π and α, we can determine the complexity class automatically, with an efficient (centralized, sequential) meta-algorithm, and we can also efficiently synthesize an asymptotically optimal distributed algorithm. Before this work, similar results were only known for local search problems (e.g., locally checkable labeling problems). The family of local optimization problems is a strict generalization of local search problems, and it contains numerous commonly studied distributed tasks, such as the problems of finding approximations of the maximum independent set, minimum vertex cover, minimum dominating set, and minimum vertex coloring.

Common definitions of the “standard” LOCAL model tend to be sloppy and even self-contradictory on one point: do the nodes update their state using an arbitrary function or a computable function? So far, this distinction has been safe to neglect, since problems where it matters seem contrived and quite different from e.g. typical local graph problems studied in this context.

By prior work, we have many results related to distributed graph algorithms for problems that can be defined with local constraints; the formal framework used in prior work is locally checkable labeling problems (LCLs), introduced by Naor and Stockmeyer in the 1990s. It is known, for example, that if we have a deterministic algorithm that solves an LCL in $o(\log n)$ rounds, we can speed it up to $O(\log^*n)$ rounds, and if we have a randomized $O(\log^*n)$ rounds algorithm, we can derandomize it for free. It is also known that randomness helps with some LCL problems: there are LCL problems with randomized complexity $Θ(\log\log n)$ and deterministic complexity $Θ(\log n)$. However, so far there have not been any LCL problems in which the use of shared randomness has been necessary; in all prior algorithms it has been enough that the nodes have access to their own private sources of randomness. Could it be the case that shared randomness never helps with LCLs? Could we have a general technique that takes any distributed graph algorithm for any LCL that uses shared randomness, and turns it into an equally fast algorithm where private randomness is enough? In this work we show that the answer is no. We present an LCL problem $Π$ such that the round complexity of $Π$ is $Ω(\sqrt n)$ in the usual randomized \local model with private randomness, but if the nodes have access to a source of shared randomness, then the complexity drops to $O(\log n)$. As corollaries, we also resolve several other open questions related to the landscape of distributed computing in the context of LCL problems. In particular, problem $Π$ demonstrates that distributed quantum algorithms for LCL problems strictly benefit from a shared quantum state. Problem $Π$ also gives a separation between finitely dependent distributions and non-signaling distributions.

The online-LOCAL and SLOCAL models are extensions of the LOCAL model where nodes are processed in a sequential but potentially adversarial order. So far, the only problem we know of where the global memory of the online-LOCAL model has an advantage over SLOCAL is 3-coloring bipartite graphs. Recently, Chang et al. [PODC 2024] showed that even in grids, 3-coloring requires Ω(log n) locality in deterministic online-LOCAL. This result was subsequently extended by Akbari et al. [STOC 2025] to also hold in randomized online-LOCAL. However, both proofs heavily rely on the assumption that the algorithm does not have access to the orientation of the underlying grid. In this paper, we show how to lift this requirement and obtain the same lower bound (against either model) even when the algorithm is explicitly given a globally consistent orientation of the grid.

We study the problem of certifying whether a graph is k-colorable with a locally checkable proof (LCP) that is able to hide the k-coloring from the verifier, in the sense that no algorithm can (completely) extract a k-coloring from the certificate. Motivated by the search for promise-free separations of extensions of the LOCAL model in the context of locally checkable labeling (LCL) problems, we also require the LCPs to satisfy what we call the strong soundness property. We focus on the case of 2-coloring and show that strong and hiding LCPs for 2-coloring exist in specific graph classes and require only O (log n)-sized certificates. Furthermore, when the input is promised to be a cycle or contains a node of degree 1, we show the existence of strong and hiding LCPs even in an anonymous network and with constant-size certificates. Despite these upper bounds, we prove that there are no strong and hiding LCPs for 2-coloring in general, regardless of certificate size. Along the way, we give a characterization of the hiding property for the general k-coloring problem that appears to be a key component for future investigations in this context.

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^\star 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^\star n)$ in the classical deterministic LOCAL model. One of many implications is that in rooted trees, $O(\log^\star n)$ locality in quantum-LOCAL is not stronger than $O(\log^\star n)$ locality in classical LOCAL.

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.

In this work, we give two results that put new limits on distributed quantum advantage in the context of the LOCAL model of distributed computing. First, we show that there is no distributed quantum advantage for any linear program. Put otherwise, if there is a quantum-LOCAL algorithm $\mathcal{A}$ that finds an $α$-approximation of some linear optimization problem $Π$ in $T$ communication rounds, we can construct a classical, deterministic LOCAL algorithm $\mathcal{A}'$ that finds an $α$-approximation of $Π$ in $T$ rounds. As a corollary, all classical lower bounds for linear programs, including the KMW bound, hold verbatim in quantum-LOCAL. Second, using the above result, we show that there exists a locally checkable labeling problem (LCL) for which quantum-LOCAL is strictly weaker than the classical deterministic SLOCAL model. Our results extend from quantum-LOCAL also to finitely dependent and non-signaling distributions, and one of the corollaries of our work is that the non-signaling model and the SLOCAL model are incomparable in the context of LCL problems: By prior work, there exists an LCL problem for which SLOCAL is strictly weaker than the non-signaling model, and our work provides a separation in the opposite direction.

Given the full topology of a network, how hard is it to test if it is evolving according to a local rule or is far from doing so? Inspired by the works of Goldreich and Ron (J. ACM, 2017) and Nakar and Ron (ICALP, 2021), we initiate the study of property testing in dynamic environments with arbitrary topologies. Our focus is on the simplest non-trivial rule that can be tested, which corresponds to the 1-BP rule of bootstrap percolation and models a simple spreading behavior: Every "infected" node stays infected forever, and each "healthy" node becomes infected if and only if it has at least one infected neighbor. Our results are subdivided into two main groups: - If we are testing a single time step of evolution, then the query complexity is O(Δ/ε) or Õ(√n/ε) (whichever is smaller), where Δ and n are the maximum degree of a node and the number of vertices in the underlying graph, respectively. We also give lower bounds for both one- and two-sided error testers that match our upper bounds up to Δ = o(√n) and Δ = O(n^{1/3}), respectively. If ε is constant, then the first of these also holds against adaptive testers. - When testing the environment over T time steps, we have two algorithms that need O(Δ^{T-1}/εT) and Õ(|E|/εT) queries, respectively, where E is the set of edges of the underlying graph. All of our algorithms are one-sided error, and all of them are also non-adaptive, with the single exception of the more complex Õ(√n/ε)-query tester for the case T = 2.

The randomized online-LOCAL model captures a number of models of computing; it is at least as strong as all of these models: - the classical LOCAL model of distributed graph algorithms, - the quantum version of the LOCAL model, - finitely dependent distributions [e.g. Holroyd 2016], - any model that does not violate physical causality [Gavoille, Kosowski, Markiewicz, DISC 2009], - the SLOCAL model [Ghaffari, Kuhn, Maus, STOC 2017], and - the dynamic-LOCAL and online-LOCAL models [Akbari et al., ICALP 2023]. In general, the online-LOCAL model can be much stronger than the LOCAL model. For example, there are locally checkable labeling problems (LCLs) that can be solved with logarithmic locality in the online-LOCAL model but that require polynomial locality in the LOCAL model. However, in this work we show that in trees, many classes of LCL problems have the same locality in deterministic LOCAL and randomized online-LOCAL (and as a corollary across all the above-mentioned models). In particular, these classes of problems do not admit any distributed quantum advantage. We present a near-complete classification for the case of rooted regular trees. We also fully classify the super-logarithmic region in unrooted regular trees. Finally, we show that in general trees (rooted or unrooted, possibly irregular, possibly with input labels) problems that are global in deterministic LOCAL remain global also in the randomized online-LOCAL model.

We give an almost complete characterization of the hardness of c-coloring χ-chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. In particular, we show that these problems do not admit any distributed quantum advantage. To do that:

Abstract Fungal automata are a variation of the two-dimensional sandpile automaton of Bak et al. (Phys Rev Lett 59(4):381–384, 1987. https://doi.org/10.1103/PhysRevLett.59.381 ). In each step toppling cells emit grains only to some of their neighbors chosen according to a specific update sequence. We show how to embed any Boolean circuit into the initial configuration of a fungal automaton with update sequence HV. In particular we give a constructor that, given the description B of a circuit, computes the states of all cells in the finite support of the embedding configuration in $$O(\log \left| {B}\right| )$$ O ( log B ) space. As a consequence the prediction problem for fungal automata with update sequence HV is $$\textsf {P}$$ P -complete. This solves an open problem of Goles et al. (Phys Lett A 384(22):126541, 2020. https://doi.org/10.1016/j.physleta.2020.126541 ).

We propose and investigate a probabilistic model of sublinear-time one-dimensional cellular automata. In particular, we modify the model of ACA (which are cellular automata that accept if and only if all cells simultaneously accept) so that every cell changes its state not only dependent on the states it sees in its neighborhood but also on an unbiased coin toss of its own. The resulting model is dubbed probabilistic ACA (PACA). We consider one- and two-sided error versions of the model (in the same spirit as the classes $\mathsf{RP}$ and $\mathsf{BPP}$) and establish a separation between the classes of languages they can recognize all the way up to $o(\sqrt{n})$ time. As a consequence, we have a $Ω(\sqrt{n})$ lower bound for derandomizing constant-time two-sided error PACAs (using deterministic ACAs). We also prove that derandomization of $T(n)$-time PACAs (to polynomial-time deterministic cellular automata) for various regimes of $T(n) = ω(\log n)$ implies non-trivial derandomization results for the class $\mathsf{RP}$ (e.g., $\mathsf{P} = \mathsf{RP}$). The main contribution is an almost full characterization of the constant-time PACA classes: For one-sided error, the class equals that of the deterministic model; that is, constant-time one-sided error PACAs can be fully derandomized with only a constant multiplicative overhead in time complexity. As for two-sided error, we identify a natural class we call the linearly testable languages ($\mathsf{LLT}$) and prove that the languages decidable by constant-time two-sided error PACAs are "sandwiched" in-between the closure of $\mathsf{LLT}$ under union and intersection and the class of locally threshold testable languages ($\mathsf{LTT}$).

Abstract The expanding cellular automata (XCA) variant of cellular automata is investigated and characterized from a complexity-theoretical standpoint. An XCA is a one-dimensional cellular automaton which can dynamically create new cells between existing ones. The respective polynomial-time complexity class is shown to coincide with $${\le _{tt}^p}(\textsf {NP})$$ ≤ tt p ( NP ) , that is, the class of decision problems polynomial-time truth-table reducible to problems in $$\textsf {NP}$$ NP . An alternative characterization based on a variant of non-deterministic Turing machines is also given. In addition, corollaries on select XCA variants are proven: XCAs with multiple accept and reject states are shown to be polynomial-time equivalent to the original XCA model. Finally, XCAs with alternative acceptance conditions are considered and classified in terms of $${\le _{tt}^p}(\textsf {NP})$$ ≤ tt p ( NP ) and the Turing machine polynomial-time class $$\textsf {P}$$ P .