How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)

Abstract.
Motivated by real world networks and use of algorithms based on random walks on
these networks we study the simple random walks on dynamic undirected graphs
with fixed underlying vertex set, i.e., graphs which are modified by inserting or
deleting edges at every step of the walk. We are interested in the expected time
needed to visit all the vertices of such a dynamic graph, the cover time, under the
assumption that the graph is being modified by an oblivious adversary. It is well
known that on connected static undirected graphs the cover time is polynomial in
the size of the graph. On the contrary and somewhat counter-intuitively, we show
that there are adversary strategies which force the expected cover time of a simple
random walk on connected dynamic graphs to be exponential. We relate this result
to the cover time of static directed graphs. In addition we provide a simple
strategy, the lazy random walk, that guarantees polynomial cover time regardless
of the changes made by the adversary.
Joint work with: Michal Kouck´y and Zvi LotkerBio:
Dr. Chen Avin received the B.Sc. degree in Communication Systems Engineering
from Ben Gurion University, Israel, in 2000. He received the M.S. and Ph.D.
degrees in computer science from the University of California, Los Angeles
(UCLA) in 2003 and 2006 respectively.
He is now a Lecturer in the Department of Communication Systems Engineering at
the Ben Gurion University since October 2006. His current research interests are:
Graphs and Networks Algorithms, Sensor Networks, Random Graphs,Complex
Systems and Random Walks.
Host: Bhaskar Krishnamachari

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

Audiences: Everyone Is Invited

Contact: Rahul Jain