Speaker: He Sun Max-Planck Institut for Informatics, Germany
Time: 2011-09-15 13:30-2011-09-15 14:30
Venue: FIT 1-222

Abstract:

We consider the classical rumor spreading problem, in which a ``rumor" must be disseminated to all n nodes of a given network. In push-protocols for rumor spreading, in each round, every node that knows the rumor sends it to one of its neighbors. We devise two simple push-protocols, in which nodes use pairwise independent hash functions or a pseudo-random generator to determine the recipients of their messages. For several well-studied topologies, our algorithm uses exponentially fewer random bits than previous protocols. For example, in complete graphs, hypercubes, expanders, and random graphs only a polylogarithmic number of random bits are needed in total to spread the rumor in O(log n) rounds with high probability. Previous explicit algorithms require \Omega(n) random bits to achieve the same round complexity. For the complete graph, the amount of randomness used by our algorithm is within an O(log n)-factor of the theoretical minimum determined by Giakkoupis and Woelfel.

Short Bio:

He Sun received his PhD degree from Fudan University in 2009 and now he is a Postdoctoral Fellow at Max Planck Institute for Informatics in Saarbruecken, Germany. His research area is in algorithms and complexity. Specific topics include randomized algorithms, expander graphs, and computational geometry.