ARC Seminar: Andreas Galanis (Oxford)

Algorithms & Randomness Center (ARC)

Andreas Galanis (Oxford)

Thursday, September 21, 2017

Klaus 1116 West - 11:00 am


Title:   Random Walks on Small World Networks



We study the mixing time of random walks on small-world networks modelled as follows: starting with the 2-dimensional periodic grid, each pair of vertices {u,v} with distance d>1 is added as a "long-range" edge with probability proportional to d^(-r), where r>=0 is a parameter of the model. Kleinberg studied a close variant of this network model and proved that the decentralised routing time is O((logn)^2) when r=2 and n^Ω(1) when r\neq 2. Here, we prove that the random walk also undergoes a phase transition at r=2, but in this case the phase transition is of a different form. We establish that the mixing time is Θ(logn) for r<2, O((logn)^4) for r=2 and n^{Ω(1)} for r>2.

Joint work with Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, and Eric Vigoda.


Speaker's Webpage

Videos of recent talks are available at:

Click here to subscribe to the seminar email list:

Event Details


  • Thursday, September 21, 2017
    11:00 am - 12:00 pm
Location: Klaus 1116 West

For More Information Contact