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

[[seminaires:distribue:index|Calcul distribué]]\\
Jeudi 4 juin 2020, 14 heures, Online\\
**Mikaël Rabie** (LIP6, Sorbonne Université) //Lower bounds for maximal matchings and maximal independent sets//
<button type="link" size="xs" collapse="b19-3499">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b19-3499" collapsed="true">
<well size="sm">
There are distributed graph algorithms for finding maximal matchings and maximal independent sets in O(Delta+log^*n) communication rounds; here n is the number of nodes and Delta is the maximum degree. The lower bound by Linial (1987, 1992) shows that the dependency on n is optimal: these problems cannot be solved in o(log^*n) rounds even if Delta=2. However, the dependency on Delta is a long-standing open question, and there is currently an exponential gap between the upper and lower bounds. We prove that the upper bounds are tight. In this presentation, I will first provide previous results on the bounds depending on n, before providing the tools and ideas we used for the case of Delta dependency. This is a joint work with Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, and Jukka Suomela. These results got the Best Paper award at FOCS 2019.
</well>
</collapse>