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 …

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

There is a rapidly growing need for scalable algorithms that solve classical graph problems,
such as maximum matching and minimum vertex cover, on massive graphs. For massive …

Many modern parallel systems, such as MapReduce, Hadoop and Spark, can be modeled
well by the MPC model. The MPC model captures well coarse-grained computation on large …

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 …

Correlation clustering is a central topic in unsupervised learning, with many applications in
ML and data mining. In correlation clustering, one receives as input a signed graph and the …

We design a generic method to reduce the task of finding weighted matchings to that of
finding short augmenting paths in unweighted graphs. This method enables us to provide …

We introduce a method for “sparsifying” distributed algorithms and exhibit how it leads to
improvements that go past known barriers in two algorithmic settings of large-scale graph …

Identifying the connected components of a graph, apart from being a fundamental problem
with countless applications, is a key primitive for many other algorithms. In this paper, we …

We present the first conditional hardness results for massively parallel algorithms for some
central graph problems including (approximating) maximum matching, vertex cover …