We present a simple polylogarithmic-time deterministic distributed algorithm for network
decomposition. This improves on a celebrated 2 O (√ log n)-time algorithm of Panconesi …

We present an Õ (log2 n) round deterministic distributed algorithm for the maximal
independent set problem. By known reductions, this round complexity extends also to …

We develop a general deterministic distributed method for locally rounding fractional
solutions of graph problems for which the analysis can be broken down into analyzing pairs …

Recently, Brandt et al. STOC'16provedalowerboundforthedistributedLov…,whichhasbeenconjecturedtobetightforsuffici…
'17.Attheheartoftheirresultliesaspeeduptechniq…,forgraphsofgirthatleast2t+2,transformsanyt …

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

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 describe approximation algorithms in Linial's classic LOCAL model of distributed
computing to find maximum-weight matchings in a hypergraph of rank r. Our main result is a …

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 …