Cover Time and Broadcast Time

Robert Elsässer, Thomas Sauerwald

We introduce a new technique for bounding the cover time of random walks by relating it to the runtime of randomized broadcast. In particular, we strongly confirm for dense graphs…