Algorithmes et structures discrètes
Mardi 16 novembre 2021, 13 heures 30, Room 234C, Halle aux farines
Pole Day (ASD) 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)
Algorithmes et structures discrètes
Mardi 15 juin 2021, 14 heures, Salle 3052
Magnús Halldórsson (Reykjavik University) New Vistas in Distributed Graph Coloring
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.
The seminar will be available online by the following ZOOM-link:
https://u-paris.zoom.us/j/84049775680?pwd=Yk5lMDhlZUNQRGMyelExMVdoM2poQT09