Massively Parallel Algorithms for Symmetry-Breaking Problems in Sparse Graphs

24^th March 2026, 13:00 EEE Building, Elec201
Jara Uitto
Aalto University

Abstract

The Massively Parallel Computation (MPC) model is a well-established mathematical abstraction of modern frameworks of parallel computation. An input graph is partitioned among a set of machines that communicate with each other to collectively solve a graph problem. The crux of the model is that each machine has bounded space, that is, each machine only sees a tiny fraction of the input and has limited communication bandwidth.

Central problems in this model include symmetry-breaking problems such as finding large independent sets, matchings, and colorings. In this talk, I will survey classic results and recent developments on those problems with a particular focus on sparse input graphs.