{"438131":{"#nid":"438131","#data":{"type":"event","title":"ARC Colloquium: Charilaos Efthymiou - Georgia Tech","body":[{"value":"\u003Cp\u003ENote: Talk will be held in Marcus 1117-1118.\u003C\/p\u003E\u003Ch6 align=\u0022center\u0022\u003E\u003Cstrong\u003E\u0026nbsp;Algorithms \u0026amp; Randomness Center (ARC)\u003C\/strong\u003E\u003C\/h6\u003E\u003Ch5 align=\u0022center\u0022\u003ECharilaos Efthymiou \u2013 Georgia Tech\u003C\/h5\u003E\u003Ch6 align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, September 14, 2015\u003C\/strong\u003E\u003C\/h6\u003E\u003Ch6 align=\u0022center\u0022\u003E\u003Cstrong\u003EMarcus 1117 \u0026amp; 1118 - 1:00 pm\u003C\/strong\u003E\u003C\/h6\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\u003EReconstruction thresholds for the random colourings of G(n,m)\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EIn this talk we consider the reconstruction problem for the random colourings of a random graph G(n,m) of\u0026nbsp; degree d.\u003C\/p\u003E\u003Cp\u003EFor some k-colourable graph G,\u0026nbsp; the reconstruction problem studies the correlation between the assignment of a single vertex in G and that of its neighbours at distance r, under the uniform measure over the k-colourings of G. This is point to set correlation.\u003C\/p\u003E\u003Cp\u003EWhen the correlation persists as r grows, then we have reconstruction, otherwise we have non-reconstruction.\u003C\/p\u003E\u003Cp\u003EIt has been conjecture from statistical physics that for typical instances of G(n,m)\u0026nbsp; the transition from non-reconstruction to reconstruction exhibits a threshold behavior. That is, there is a critical value k_0, which depends on the expected degree d, such that the following is true:\u0026nbsp; When k\u0026gt;k_0 there is non-reconstruction while when k\u0026lt;k_0 there is reconstruction.\u003C\/p\u003E\u003Cp\u003EThe aforementioned phase transition has been related to the performance of local search algorithms as well as the shattering phenomenon in the solution space of the k-colourings.\u003C\/p\u003E\u003Cp\u003EIn this talk I discuss our recent results which show that the phase transition from statistical physics is indeed correct. Moreover, the point where this phase transition occurs, up to smaller order terms, is exactly at the point where it has been conjectured to be.\u003C\/p\u003E\u003Cp\u003EThe first step in our approach is to show that the Gibbs distribution over the k-colouring of G(n,m) converges locally to the Gibbs distribution over the k-colourings of a Poisson(d) Galton-Watson tree\u0026nbsp; T(d), for a wide range of\u0026nbsp; k. This allows to reduce our initial problem to studying the reconstruction on T(d). The second step is to establish the reconstruction threshold for the colourings of T(d).\u003C\/p\u003E\u003Cp\u003EThis talk is based on 2 recent works of mine.\u0026nbsp; One of them is a joint work with Amin Coja-Oghlan and Nor Jaafari.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Marcus 1117 \u0026 1118 at 1 pm (Note: different location)"}],"uid":"27466","created_gmt":"2015-08-20 15:28:05","changed_gmt":"2017-04-13 21:18:39","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-09-14T14:00:00-04:00","event_time_end":"2015-09-14T15:00:00-04:00","event_time_end_last":"2015-09-14T15:00:00-04:00","gmt_time_start":"2015-09-14 18:00:00","gmt_time_end":"2015-09-14 19:00:00","gmt_time_end_last":"2015-09-14 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":""}}}