{"641623":{"#nid":"641623","#data":{"type":"event","title":"ARC and Indo-US Virtual Center Seminar: Zongchen Chen (Georgia Tech)","body":[{"value":"\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) and\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EIndo-US Virtual Center Seminar\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EZonchen Chen (Georgia Tech)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, November 30, 2020\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EVirtual via BlueJeans - 11:00am\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; \u003C\/strong\u003EOptimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u0026nbsp; \u003C\/strong\u003EWe consider the Glauber dynamics (also called Gibbs sampling) for sampling from a discrete high-dimensional space, where in each step\u0026nbsp;one variable is chosen uniformly at random and gets updated conditional on all other variables. We show an optimal mixing time bound for\u0026nbsp;the Glauber dynamics in a variety of settings. Our work presents an improved version of the spectral independence approach of Anari et al.\u0026nbsp;(2020) and shows O(nlogn) mixing time for graphical models\/spin systems on any n-vertex graph of bounded degree when the maximum\u0026nbsp;eigenvalue of an associated influence matrix is bounded. Our proof approach combines classic tools of entropy tensorization\/factorization\u0026nbsp;and recent developments of high-dimensional expanders.\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nAs an application of our results, for the hard-core model on independent sets weighted by a fugacity lambda, we establish O(nlogn) mixing\u0026nbsp;time for the Glauber dynamics on any n-vertex graph of constant maximum degree D when lambda\u0026lt;lambda_c(D) where lambda_c(D) is\u0026nbsp;the critical point for the uniqueness\/non-uniqueness phase transition on the D-regular tree. More generally, for any antiferromagnetic 2-spin\u0026nbsp;system we prove O(nlogn) mixing time of the Glauber dynamics on any bounded degree graph in the corresponding tree uniqueness\u0026nbsp;region. Our results apply more broadly; for example, we also obtain O(nlogn) mixing for sampling random q-colorings of triangle-free\u0026nbsp;graphs of maximum degree D when the number of colors satisfies q \u0026gt; aD where a = 1.763\u0026hellip;, and O(mlogn) mixing for generating random\u0026nbsp;matchings of any graph with bounded degree and m edges.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/sites.google.com\/view\/zongchenchen\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=\u0022http:\/\/arc.gatech.edu\/node\/121\u0022\u003Ehttp:\/\/arc.gatech.edu\/node\/121\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@Klauscc.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":"Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion: Virtual via Bluejeans @ 11:00am"}],"uid":"27544","created_gmt":"2020-11-24 14:12:27","changed_gmt":"2020-11-24 14:14:17","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2020-11-30T11:00:00-05:00","event_time_end":"2020-11-30T12:00:00-05:00","event_time_end_last":"2020-11-30T12:00:00-05:00","gmt_time_start":"2020-11-30 16:00:00","gmt_time_end":"2020-11-30 17:00:00","gmt_time_end_last":"2020-11-30 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":"177814","name":"Postdoc"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}