We study connections between distributed local algorithms, finitary factors of iid processes,
and descriptive combinatorics in the context of regular trees. We extend the Borel …

A rich line of work has been addressing the computational complexity of locally checkable
labelings (LCLs), illustrating the landscape of possible complexities. In this paper, we study …

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 …

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 …

We extend the theory of locally checkable labeling problems (LCLs) from the classical
LOCAL model to a number of other models that have been studied recently, including the …

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 …

We give practical, efficient algorithms that automatically determine the asymptotic distributed
round complexity of a given locally checkable graph problem in the $[\Theta (\log n),\Theta …

The locality of a graph problem is the smallest distance T such that each node can choose
its own part of the solution based on its radius-T neighborhood. In many settings, a graph …

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 …

Over the past decade, a long line of research has investigated the distributed complexity
landscape of locally checkable labeling (LCL) problems on bounded-degree graphs …