Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, September 17, 2020, 12:15 pm
Duration: 30 minutes
Location: Zoom: conference room
Speaker: Sebastian Brandt
Given a graph G = (V,E), an (a,b)-ruling set is a subset S of V such that the distance between any two vertices in S is at least a, and the distance between any vertex in V and the closest vertex in S is at most b. Ruling sets are a generalization of maximal independent sets (which are (2,1)-ruling sets) and constitute an important building block of many distributed algorithms. The recent breakthrough on network decompositions by Rozhon and Ghaffari [STOC'20] implies that, in the distributed LOCAL model, ruling sets can be computed deterministically in polylogarithmic time, for a wide range of parameters a, b. In this talk, we present polylogarithmic lower bounds for the deterministic computation of ruling sets, and Omega(poly(log log n)) lower bounds for the randomized computation of ruling sets, both in the LOCAL model, improving on the previously best known lower bounds of Omega(log*n)) by Linial [FOCS'87] and Naor [J.Disc.Math.'91]. In the special case of maximal independent sets, such lower bounds were already known; however, our lower bounds are the first (beyond Omega(log*n)) that are also applicable on trees. This is joint work with Alkida Balliu and Dennis Olivetti.
Automatic MiSe System Software Version 1.4803M | admin login