~~NOCACHE~~
/* DO NOT EDIT THIS FILE             */

[[en:seminaires:asd:index|Algorithms and discrete structures]]\\
Tuesday November 16, 2021, 1:30PM, Room 234C, Halle aux farines\\
**Pole Day** (ASD) //Journée du pôle Algorithmes et structures discrètes 2021//
<button type="link" size="xs" collapse="b26-4102">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b26-4102" collapsed="true">
<well size="sm">
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)
</well>
</collapse>


[[en:seminaires:asd:index|Algorithms and discrete structures]]\\
Tuesday June 15, 2021, 2PM, Salle 3052\\
**Magnús Halldórsson** (Reykjavik University) //New Vistas in Distributed Graph Coloring//
<button type="link" size="xs" collapse="b26-4103">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b26-4103" collapsed="true">
<well size="sm">
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.
</well>
</collapse>
The seminar will be available online by the following ZOOM-link:

https://u-paris.zoom.us/j/84049775680?pwd=Yk5lMDhlZUNQRGMyelExMVdoM2poQT09