{"446271":{"#nid":"446271","#data":{"type":"event","title":"ARC Colloquium: Yitong Yin \u2013 Nanjing University","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) \u003C\/strong\u003E\u003C\/p\u003E\u003Ch2 align=\u0022center\u0022\u003EYitong Yin \u2013 Nanjing University\u003C\/h2\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, September 28, 2015\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 West - 1:00 pm\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003E(Refreshments will be served in Klaus 2222 at 2 pm)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003ECounting hypergraph matchings up to uniqueness threshold\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EWe study the problem of approximately counting hypergraph matchings with an activity parameter $\\lambda$ in hypergraphs of bounded maximum degree and bounded maximum size of hyperedges. This problem unifies two important statistical physics models in approximate counting: the hardcore model (graph independent sets) and the monomer-dimer model (graph matchings).\u003C\/p\u003E\u003Cp\u003EWe show for this model the critical activity $\\lambda_c= \\frac{d^d}{k (d-1)^{d+1}}$ is the threshold for the uniqueness of Gibbs measures on the infinite $(d+1)$-uniform $(k+1)$-regular hypertree. And we show that when $\\lambda\u0026lt;\\lambda_c$ the model exhibits strong spatial mixing at an exponential rate and there is an FPTAS for the partition function of the model on all hypergraphs of maximum degree at most $k+1$ and maximum \u0026nbsp;edge size at most $d+1$. Assuming NP$\\neq$RP, there is no FPRAS for the partition function of the model when $\\lambda \u0026gt; 2\\lambda_c$ on above family of hypergraphs .\u003C\/p\u003E\u003Cp\u003ETowards closing this gap and obtaining a tight transition of approximability, we study the local weak convergence from an infinite sequence of random finite hypergraphs to the infinite uniform regular hypertree with specified symmetry, and prove a surprising result: the existence of such local convergence is fully characterized by the reversibility of the uniform random walk on the infinite hypertree projected on the symmetry classes. We also give explicit constructions sequence of random finite hypergraphs with proper local convergence property when the reversibility condition is satisfied.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Klaus 1116 West at 1 pm"}],"uid":"27466","created_gmt":"2015-09-10 09:47:51","changed_gmt":"2017-04-13 21:18:21","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-09-28T14:00:00-04:00","event_time_end":"2015-09-28T15:00:00-04:00","event_time_end_last":"2015-09-28T15:00:00-04:00","gmt_time_start":"2015-09-28 18:00:00","gmt_time_end":"2015-09-28 19:00:00","gmt_time_end_last":"2015-09-28 19:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"related_links":[{"url":"http:\/\/www.arc.gatech.edu\/","title":"Algorithms \u0026 Randomness Center (ARC)"}],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"111051","name":"Algorithm and Randomness Center"},{"id":"4265","name":"ARC"},{"id":"115001","name":"Computational Complexity"},{"id":"114991","name":"Computational Learning Theory"},{"id":"109","name":"Georgia Tech"}],"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\u003Cbr \/\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}