{"436081":{"#nid":"436081","#data":{"type":"event","title":"ARC Colloquium: Andreas Galanis - University of Oxford","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) Colloquium\u003C\/strong\u003E\u003C\/p\u003E\u003Ch2 align=\u0022center\u0022\u003EAndreas Galanis\u0026nbsp;\u2013\u0026nbsp;University of Oxford\u003C\/h2\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EWednesday, August 26, 2015\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 2447 - 2:00 pm\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003E\u0026nbsp;Title:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003ESwendsen-Wang Algorithm on the Mean-Field Potts Model\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EThis talk will focus on the q-state ferromagnetic Potts model on the n-vertex complete graph known as the mean-field (Curie-Weiss) model. We analyze the Swendsen-Wang algorithm which is a Markov chain that utilizes the random cluster representation for the ferromagnetic Potts model to recolor large sets of vertices in one step and potentially overcomes obstacles that inhibit single-site Glauber dynamics.\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;The case q=2 (the Swendsen-Wang algorithm for the ferromagnetic Ising model) undergoes a slow-down at a critical temperature beta=betac (Long et al., 2014), but yet still has polynomial mixing time at all (inverse) temperatures beta\u0026gt;0 (Cooper et al., 2000).\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;In contrast, for q\u0026gt;=3 there are two critical temperatures 0\u0026lt;betau\u0026lt;betarc that are relevant (these correspond to phase transitions on the infinite tree). We prove that the mixing time of the Swendsen-Wang algorithm for the ferromagnetic Potts model on the n-vertex complete graph satisfies:\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E(i) O(log n) for beta\u0026lt;betau, (ii) O(n^{1\/3}) for beta=betau, (iii) exp(n^(Omega(1))) for betau\u0026lt;beta\u0026lt;betarc, and (iv) O(log n) for beta\u0026gt;=betarc.\u0026nbsp;These results complement refined results of Cuff et al. (2012) on the mixing time of the Glauber dynamics for the ferromagnetic Potts model.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;The most interesting aspect of our analysis is at the critical temperature beta=betau, which requires a delicate choice of a potential function to balance the conflating factors for the slow drift away from a fixed point (which is repulsive but not Jacobian repulsive): close to the fixed point the variance from the percolation step dominates and sufficiently far from the fixed point the dynamics of the size of the dominant color class takes over.\u003C\/p\u003E\u003Cp\u003EJoint work with Daniel Stefankovic and Eric Vigoda.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Klaus 2447 at 4 pm (Note: time and location are different than usual)"}],"uid":"27466","created_gmt":"2015-08-18 13:42:48","changed_gmt":"2017-04-13 21:18:45","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-08-26T15:05:00-04:00","event_time_end":"2015-08-26T16:00:00-04:00","event_time_end_last":"2015-08-26T16:00:00-04:00","gmt_time_start":"2015-08-26 19:05:00","gmt_time_end":"2015-08-26 20:00:00","gmt_time_end_last":"2015-08-26 20:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"112751","name":"(ARC)"},{"id":"111051","name":"Algorithm and Randomness Center"},{"id":"115001","name":"Computational Complexity"},{"id":"114991","name":"Computational Learning Theory"},{"id":"109","name":"Georgia Tech"},{"id":"168064","name":"Swendsen-Wang algorithm"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EDani Denton\u003C\/p\u003E\u003Cp\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}