Abstract The Maximal Independent Set (MIS) problem is one of the basics in the study of
locality in distributed graph algorithms. This paper presents a very simple randomized …

We study the computation power of the congested clique, a model of distributed computation
where n players communicate with each other over a complete network in order to compute …

We present O (loglog n)-round algorithms in the Massively Parallel Computation (MPC)
model, with Õ (n) memory per machine, that compute a maximal independent set, a 1+ ε …

A distributed network is modeled by a graph having n nodes (processors) and diameter D.
We study the time complexity of approximating weighted (undirected) shortest paths on …

In this work, we use algebraic methods for studying distance computation and subgraph
detection tasks in the congested clique model. Specifically, we adapt parallel matrix …

In this paper, we present new randomized algorithms that improve the complexity of the
classic (Δ+ 1)-coloring problem, and its generalization (Δ+ 1)-list-coloring, in three well …

We present a deterministic (1+ o (1))-approximation O (n 1/2+ o (1)+ D 1+ o (1))-time
algorithm for solving the single-source shortest paths problem on distributed weighted …

For over a decade now we have been witnessing the success of massive parallel
computation (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the …

We present a distributed randomized algorithm finding Minimum Spanning Tree (MST) of a
given graph in O (1) rounds, with high probability, in the congested clique model. The input …

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 …