Select a calendar:
Filter June Events by Event Type:
SUNMONTUEWEDTHUFRISAT
Events for June 14, 2007
-
Many Random Walks Are Faster Than One
Thu, Jun 14, 2007 @ 10:30 AM - 11:30 AM
Ming Hsieh Department of Electrical and Computer Engineering
Workshops & Infosessions
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
