{"595529":{"#nid":"595529","#data":{"type":"event","title":"ARC Seminar: Andreas Galanis (Oxford)","body":[{"value":"\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EAndreas Galanis (Oxford)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EThursday, September 21, 2017\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 West - 11:00 am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle:\u0026nbsp;\u0026nbsp; \u003C\/strong\u003E\u003Cem\u003ERandom Walks on Small World Networks\u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u0026nbsp; \u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003EWe 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\u0026gt;1 is added as a \u0026quot;long-range\u0026quot; edge with probability proportional to d^(-r), where r\u0026gt;=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^\u0026Omega;(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 \u0026Theta;(logn) for r\u0026lt;2, O((logn)^4) for r=2 and n^{\u0026Omega;(1)} for r\u0026gt;2.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EJoint work with Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, and Eric Vigoda.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E--------------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022http:\/\/www.cs.ox.ac.uk\/people\/andreas.galanis\/myindex.html\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Random Walks on Small World Networks (Klaus 1116 East at 11am)"}],"uid":"27544","created_gmt":"2017-09-06 12:41:22","changed_gmt":"2017-09-13 19:15:32","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2017-09-21T12:00:00-04:00","event_time_end":"2017-09-21T13:00:00-04:00","event_time_end_last":"2017-09-21T13:00:00-04:00","gmt_time_start":"2017-09-21 16:00:00","gmt_time_end":"2017-09-21 17:00:00","gmt_time_end_last":"2017-09-21 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003E\u003Ca href=\u0022mailto:ftonge3@cc.gatech.edu\u0022\u003Eftonge3@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E\r\n","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}