Please note: This seminar will take place in DC 3317 and online.
Maxime Roland René Flin
Reykjavik University, Iceland
The celebrated palette sparsification result of [Assadi, Chen, and Khanna SODA'19] shows that to compute a Delta+1 coloring of the graph, where Delta denotes the maximum degree, it suffices if each node limits its color choice to O(log n) independently sampled colors. They showed that it is possible to color the resulting sparsified graph — with edges between neighbors that sampled a common color — and obtain a Delta+1 coloring for the original graph. However, to compute the actual coloring, that information must be gathered at a single location for centralized processing.
In this talk, I will explain how we can compute such a coloring distributively. The Distributed Palette Sparsification Theorem states that after palette sparsification with O(log^2 n) colors, there exists a O(log^2 Delta + log^3 log n)-round CONGEST algorithm on the sparsified graph that computes the coloring. We will see how this relates to the issue of distributively computing a perfect matching in a random graph.
In addition to combinatorial insight about palette sparsification, our theorem deepens the connections between sublinear and distributed coloring algorithms: it provides the first poly(log n)-round coloring algorithms in known constrained distributed models where vertices cannot afford to communicate on all their adjacent edges.
No prior knowledge about palette sparsification or distributed algorithms is required.
Based on joint work with Mohsen Ghaffari, Magnus M. Halldorsson, Fabian Kuhn, and Alexandre Nolin.