*Result*: Communication Complexity of Quasirandom Rumor Spreading.

*We consider rumor spreading on random graphs and hypercubes in the quasirandom phone call model. In this model, every node has a list of neighbors whose order is specified by an adversary. In step i every node opens a channel to its ith neighbor (modulo degree) on that list, beginning from a randomly chosen starting position. Then, the channels can be used for bi-directional communication in that step. The goal is to spread a message efficiently to all nodes of the graph. For random graphs (with sufficiently many edges) we present an address-oblivious algorithm with runtime O(log n) that uses at most O( nloglog n) message transmissions. For hypercubes of dimension log n we present an address-oblivious algorithm with runtime O(log n) that uses at most O( n(loglog n)) message transmissions. Together with a result of Elsässer (Proc. of SPAA'06, pp. 148-157, ), our results imply that for random graphs the communication complexity of the quasirandom phone call model is significantly smaller than that of the standard phone call model. [ABSTRACT FROM AUTHOR]*