Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, August 28, 2014, 12:15 pm
Duration: 30 minutes
Location: LFW C4
Speaker: Benjamin Doerr (Ecole Polytechnique de Paris)
We return to the super-classic problem of spreading a rumor randomly in a complete graph via the push-process. That is, we start with one node being informed, and then in each round of the process, each informed node calls a random other node and informs it (given that is was not already). Increasingly technical results by Frieze and Grimmet (1985) and Pittel (1987) prove that log2(n) + ln(n) + o(log n) respectively log2(n) + ln(n) + h(n) rounds suffice with probability 1-o(1), where h can be any function tending to infinity. In this work, we give a substantially simpler proof of a more precise result. It in particular implies that an expected number of log2(n) + ln(n) + O(1) rounds suffices.
Automatic MiSe System Software Version 1.4803M | admin login