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 …

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 …

Recent research revealed the existence of gaps in the complexity landscape of locally
checkable labeling (LCL) problems in the LOCAL model of distributed computing. For …

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 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 …

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 …

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 …