Over the past 30 years numerous algorithms have been designed for symmetry breaking
problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge …

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 …

The gap between the known randomized and deterministic local distributed algorithms
underlies arguably the most fundamental and central open question in distributed graph …

This paper is centered on the complexity of graph problems in the well-studied LOCAL
model of distributed computing, introduced by Linial [FOCS'87]. It is widely known that for …

The celebrated time hierarchy theorem for Turing machines states, informally, that more
problems can be solved given more time. The extent to which a time hierarchy--type theorem …

The (∆+ 1)-coloring problem is a fundamental symmetry breaking problem in distributed
computing. We give a new randomized coloring algorithm for (∆+ 1)-coloring running in O …

We study a family of closely-related distributed graph problems, which we call degree
splitting, where roughly speaking the objective is to partition (or orient) the edges such that …

Locally Checkable Labeling (LCL) problems include essentially all the classic problems of
$\mathsf {LOCAL} $ distributed algorithms. In a recent enlightening revelation, Chang and …

We present the first conditional hardness results for massively parallel algorithms for some
central graph problems including (approximating) maximum matching, vertex cover …

This paper addresses the cornerstone family of local problems in distributed computing, and
investigates the curious gap between randomized and deterministic solutions under …