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 …

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 …

Linial's famous color reduction algorithm reduces a given $ m $-coloring of a graph with
maximum degree $\Delta $ to a $ O (\Delta^ 2\log m) $-coloring, in a single round in the …

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 …

We prove several new tight or near-tight distributed lower bounds for classic symmetry
breaking problems in graphs. As a basic tool, we first provide a new insightful proof that any …

Given a graph G=(V,E), an (α,β)-ruling set is a subset S⊆V such that the distance between
any two vertices in S is at least α, and the distance between any vertex in V and the closest …

In this article, we present a deterministic algorithm to compute an O (k Δ)-vertex coloring in O
(Δ/k)+ log* n rounds, where Δ is the maximum degree of the network graph and k≥ 1 can be …

We provide new deterministic algorithms for the edge coloring problem, which is one of the
classic and highly studied distributed local symmetry breaking problems. As our main result …

We give a randomized Δ-coloring algorithm in the LOCAL model that runs in poly log log n
rounds, where n is the number of nodes of the input graph and Δ is its maximum degree …

We investigate the distributed complexity of maximal matching and maximal independent set
(MIS) in hypergraphs in the LOCAL model. A maximal matching of a hypergraph H=(VH, EH) …