Tight bounds for rumor spreading in graphs of a given conductance

We study the connection between the rate at which a rumor spreads throughout a graph and the conductance of the graph -- a standard measure of a graph's expansion properties. We show that for any n-node graph with conductance phi, the classical PUSH-PULL algorithm distributes a rumor to all nodes of the graph in O(phi^(-1) log(n)) rounds with high probability (w.h.p.). This bound improves a recent result of Chierichetti, Lattanzi, and Panconesi [STOC 2010], and...