In this paper we present efficient distributed algorithms for classical symmetry breaking
problems, maximal independent sets (MIS) and ruling sets, in power graphs. We work in the …

We show fast deterministic algorithms for fundamental problems on forests in the
challenging low-space regime of the well-known Massive Parallel Computation (MPC) …

We present the first local problem that shows a super-constant separation between the
classical randomized LOCAL model of distributed computing and its quantum counterpart …

Over the past decade, a long line of research has investigated the distributed complexity
landscape of locally checkable labeling (LCL) problems on bounded-degree graphs …

We present a deterministic algorithm for solving a wide range of dynamic programming
problems in trees in O (log D) rounds in the massively parallel computation model (MPC) …

This text provides an introduction to the field of distributed local algorithms--an area at the
intersection of theoretical computer science and discrete mathematics. We collect many …

We study the problem of finding connected components in the Adaptive Massively Parallel
Computation (AMPC) model. We show that when we require the total space to be linear in …

The node-averaged complexity of a problem captures the number of rounds nodes of a
graph have to spend on average to solve the problem in the LOCAL model. A challenging …

Symmetry breaking is a central theme in distributed graph algorithms. Classical symmetry
breaking problems include maximal independent set (MIS), coloring and maximal matching …