Show simple item record

dc.contributor.authorGalanis, Andreas
dc.date.accessioned2017-09-27T19:09:24Z
dc.date.available2017-09-27T19:09:24Z
dc.date.issued2017-09-21
dc.identifier.urihttp://hdl.handle.net/1853/58793
dc.descriptionPresented on September 21, 2017 at 11:00 a.m. in the Klaus Advanced Computing Building, room 1116W.en_US
dc.descriptionAndreas Galanis is a postdoctoral research fellow in the Department of Computer Science at the University of Oxford, working with Leslie Ann Goldberg. His research interests are in counting and sampling, random graphs and phase transitions.en_US
dc.descriptionRuntime: 53:56 minutesen_US
dc.description.abstractWe 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.en_US
dc.format.extent53:56 minutes
dc.language.isoen_USen_US
dc.relation.ispartofseriesARC Colloquiumen_US
dc.subjectRandom graphsen_US
dc.subjectRandom walken_US
dc.titleRandom Walks on Small World Networksen_US
dc.typeLectureen_US
dc.typeVideoen_US
dc.contributor.corporatenameGeorgia Institute of Technology. Algorithms, Randomness and Complexity Centeren_US
dc.contributor.corporatenameUniversity of Oxford. Dept. of Computer Scienceen_US


Files in this item

This item appears in the following Collection(s)

  • ARC Talks and Events [64]
    Distinguished lectures, colloquia, seminars and speakers of interest to the ARC community

Show simple item record