AGCO Seminar “Distributed Symmetry Breaking on Complex Networks”

Abstract:  Symmetry-breaking problems play a central role in the theory of distributed computing. In this talk, we consider the three classical symmetry-breaking problems graph colouring, maximal independent set (MIS), and maximal matching (MM). Motivated by the observation that many algorithms perform significantly better on real-world networks than their worst-case guarantees suggest, we design and analyse randomised algorithms for these fundamental problems on hyperbolic random graphs (HRGs), a promising model for complex real-world networks.

We present the conceivable simplest randomised algorithm that solves distributed \Delta+1 colouring in only 2 rounds (https://arxiv.org/abs/2505.19109). We also present a structural property of HRGs that separates graph colouring from MIS and MM: unlike graph colouring, which can be solved in 2 rounds, both MIS and MM require \log^{\Theta(1)}\log n rounds on
HRGs (https://arxiv.org/abs/2607.09170).

Speakers: Janosch Ruff, University of Potsdam, Alemania.