Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information
Date and Time: Thursday, October 10, 2019, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Vaclav Rozhon
We present a simple polylogarithmic-time deterministic distributed algorithm for network decomposition. This improves on a celebrated exponentially slower algorithm of Panconesi and Srinivasan [STOC'93] and settles one of the long-standing and central questions in distributed graph algorithms. It also leads to the first polylogarithmic-time deterministic distributed algorithms for numerous other graph problems, hence resolving several open problems, including Linial's well-known question about the deterministic complexity of maximal independent set [FOCS'87].
Put together with the results of Ghaffari, Kuhn, and Maus [STOC'17] and Ghaffari, Harris, and Kuhn [FOCS'18], we get a general distributed derandomization result that implies P-RLOCAL = P-LOCAL. That is, for any distributed problem whose solution can be checked in polylogarithmic-time, any polylogarithmic-time randomized algorithm can be derandomized to a polylogarithmic-time deterministic algorithm.
By known connections, our result leads also to substantially faster randomized algorithms for a number of fundamental problems including (Δ+1)-coloring, MIS, and Lovász Local Lemma.
Joint work with Mohsen Ghaffari
Automatic MiSe System Software Version 1.4803M | admin login