Logo: University of Southern California

Events Calendar


  • 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

    Add to Google CalendarDownload ICS File for OutlookDownload iCal File

Return to Calendar