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 …

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

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 consider locally checkable labeling LCL problems in the LOCAL model of distributed
computing. Since 2016, there has been a substantial body of work examining the possible …

We show fast deterministic algorithms for fundamental problems on forests in the
challenging low-space regime of the well-known Massive Parallel Computation (MPC) …

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 …

We present a poly $\log\log n $ time randomized CONGEST algorithm for a natural class of
Lovasz Local Lemma (LLL) instances on constant degree graphs. This implies, among other …

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 …