Events Calendar

Many Random Walks Are Faster Than One

Abstract:
We consider a fundamental new question regarding random walks on graphs:
How long does it take for several independent random walks to cover a whole
graph? We study the {\em cover time}, the expected amount of 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 nearly
linear in the number of the parallel walks. We demonstrate that an
exponential speed up is sometimes possible, and that there are natural
examples of graphs that only allow speed up logarithmic in the number
of walks.
This is a joint work with Alon Noga, Avin Chen; Koucky Michal, Kozma,
Gady, Tuttle, Mark R.Bio:
Zvi Lotker received his P.H.d in 2005 from Tel-Aviv university. He is now an
lecturer in the CSE department at Ben Gurion University, Israel. His
main research interests are in distributed computing.Host: Prof. Bhaskar Krishnamachari, Ext. 12528 http://engineering.usc.edu/calendar/

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Shane Goodoff