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 …

Any graph with maximum degree Δ admits a proper vertex coloring with Δ+ 1 colors that can
be found via a simple sequential greedy algorithm in linear time and space. But can one find …

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

We present a simple deterministic distributed algorithm that computes a (Δ+1)-vertex
coloring in O(log^2Δ.log\n) rounds. The algorithm can be implemented with O(log\n)-bit …

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 …

Recent papers have addressed different variants of the (Δ+ 1)-edge-colouring problem by
concatenating or gluing together many Vizing chains to form what Bernshteyn coined multi …

We design fast dynamic algorithms for proper vertex and edge colorings in a graph
undergoing edge insertions and deletions. In the static setting, there are simple linear time …

Vertex coloring is one of the classic symmetry breaking problems studied in distributed
computing. In this paper we present a new algorithm for (Δ+ 1)-list coloring in the …

We present a new approach to randomized distributed graph coloring that is simpler and
more efficient than previous ones. In particular, it allows us to tackle the (deg+ 1)-list-coloring …