Journée du pôle Algorithmes et structures discrètes 2021

Tuesday November 16, 2021 · Room 234C, Halle aux farines

13:30-14:00 - Mikael Rabie
14:00-14:30 - Matej Stehlik

14:40 – 15:10 Informal introduction of new postdocs and docs

15:15-15:45 - Adrian Vladu
15:45-16:15 - Simon Apers

16:15 Goûter (à l'IRIF)

The first and possibly the most fundamental problem in distributed graph algorithmics is the vertex coloring problem. The nodes of a network are processes that communicate via the edges in synchronous rounds. The most basic problem is to color the network using Delta+1 colors in as few rounds a possible, where Delta is the maximum degree of the graph.

We present a new approach for randomized distributed Delta+1-coloring that is dramatically simpler than the previous best: the seminal work of Chang, Li, and Pettie (CLP) in SICOMP 2020. This approach offers numerous refinements: It matches the O(log^3 log n) round complexity in general, while on high-degree graphs (Delta » log^2 n), it uses only O(log* n) rounds. It uses small messages, i.e., works also in the CONGEST model. It also offers tradeoffs between the number of colors used, the round complexity, and the clique number of the graph.

We expect that the approach presented will lead the way towards improved results for various coloring problems in the near future.

This is based on a paper at STOC'21, joint work with Fabian Kuhn, Yannic Maus, and Tigran Tonoyan; and a more recent one on arXiv, joint with Alexandre Nolin, and Tigran Tonoyan.