## Abstract / Description of output

We consider the classical rumor spreading problem, where a piece of information must be disseminated from a single node to all

Previous explicit algorithms, e.g., [10, 17, 6, 15], require Ω(

algorithm is within an O(log n)-factor of the theoretical minimum determined by Giakkoupis and Woelfel [15].

*n*nodes of a given network. We devise two simple push-based protocols, in which nodes choose the neighbor they send the information to in each round using pairwise independent hash functions, or a pseudo-random generator, respectively. For several wellstudied topologies our algorithms use exponentially fewer random bits than previous protocols. For example, in complete graphs, 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, e.g., [10, 17, 6, 15], require Ω(

*n*) random bits to achieve the same round complexity. For complete graphs, the amount of randomness used by our hashing-basedalgorithm is within an O(log n)-factor of the theoretical minimum determined by Giakkoupis and Woelfel [15].

Original language | English |
---|---|

Title of host publication | 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France |

Pages | 314-325 |

Number of pages | 12 |

DOIs | |

Publication status | Published - 2012 |

Event | STACS 2012 : Symposium on Theoretical Aspects of Computer Science - Paris, France Duration: 29 Feb 2012 → 3 Mar 2012 |

### Conference

Conference | STACS 2012 : Symposium on Theoretical Aspects of Computer Science |
---|---|

Abbreviated title | STACS 2012 |

Country/Territory | France |

City | Paris |

Period | 29/02/12 → 3/03/12 |