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 …

We consider the problem of designing fundamental graph algorithms on the model of
Massive Parallel Computation (MPC). The input to the problem is an undirected graph G …

Every graph with maximum degree Δ can be colored with (Δ+ 1) colors using a simple
greedy algorithm. Remarkably, recent work has shown that one can find such a coloring …

We show that the (degree+ 1)-list coloring problem can be solved deterministically in O (D⊙
log n⊙ log2 Δ) rounds in the CONGEST model, where D is the diameter of the graph, n the …

We present a deterministic O (log log log n)-round low-space Massively Parallel
Computation (MPC) algorithm for the classical problem of (Δ+ 1)-coloring on n-vertex …

We present a new technique to efficiently sample and communicate a large number of
elements from a distributed sampling space. When used in the context of a recent Local …

The Massively Parallel Computation (MPC) model is an emerging model that distills core
aspects of distributed and parallel computation, developed as a tool to solve combinatorial …

In this paper, we study the power and limitations of component-stable algorithms in the low-
space model of Massively Parallel Computation (MPC). Recently Ghaffari, Kuhn and Uitto …

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 …

In this work, we present a constant-round algorithm for the $2 $-ruling set problem in the
Congested Clique model. As a direct consequence, we obtain a constant round algorithm in …