• Calendar

May 15, Tuesday
12:00 – 14:00

We consider a new question regarding random walks on graphs: How long does it take for several independent random walks, starting from the same location, to cover an entire graph? We study the cover time, the expected time required to visit every node in a graph at least once, and we show that for a large collection of interesting graphs, running many random walks in parallel yields a speed-up in the cover time that is linear in the number of the parallel walks. We demonstrate that an exponential speed-up is sometimes possible, but that some natural graphs allow only a logarithmic speed-up.