Rumour spreading and graph conductance.

We show that if a connected graph with n nodes has conductance  then rumour spreading, also known as randomized broadcast, successfully broadcasts a message within O(log^4/(\phi n^6)) many steps, with high probability, using the PUSH-PULL strategy. An interesting feature of our approach is that it draws a connection between rumour spreading and the spectral sparsication procedure of Spielman and Teng.