Randomized Broadcasting and Random Walks on Cayley Graphs

First, we consider the relationship between randomized broadcasting and random walks on graphs. In particular, we prove that the runtime of the algorithm described above is upper bounded by the corresponding mixing time, up to a logarithmic factor. Then, we introduce a general class of Cayley graphs, including (among others) Star graphs, Transposition graphs, and Pancake graphs. We show that randomized broadcasting has optimal runtime on all graphs belonging to this class.

Finally, we develop a new proof technique by combining martingale tail estimates with combinatorial methods. Using this approach, we show the optimality of our algorithm on another Cayley graph. As a by product, we obtain concentration results which hold also for other Cayley graphs, e.g. Hypercubes.