Recent Advances in Distributed Coloring

-- Maxime Flin (Reykjavik University)

Time: 14:00 -- Location: LRI, 445

summary: The study of distributed graph algorithms aims to understand the limitations inherent to local computations. In a seminal paper, Linial (1992, SIAM J. Computing) introduced the LOCAL model to formalize this question. In this model, the input graph is seen as a communication network where vertices are computers. They communicate with their neighbors in synchronous rounds without loss or corruption of messages. The goal is to minimize the number of communication rounds needed before every vertex can commit to its output (e.g., decide on a color or an adjacent edge). In his paper, Linial set forth three decades of research with two central ideas: one upper bound and one lower bound on the round complexity of 3-coloring cycles.
Since then, distributed graph algorithms — and coloring problems in particular — have been intensively studied. The last decade has seen a lot of very exciting progress and ideas. In this talk, I will present some of them through the lens of distributed coloring. Concretely, we will discuss a technique called local rounding used to design poly(log n)-round deterministic algorithms. Then, we will see that randomness cannot speed up the algorithms more than exponentially and how to achieve this runtime through shattering.

Category: seminars
Tags: Team seminar graphs