Recent Advances in Distributed Coloring
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.