{"652155":{"#nid":"652155","#data":{"type":"event","title":"ARC Colloquium:David Gamarnik (MIT)","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\u003EDavid Gamarnik (MIT)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, February 14, 2022\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East - 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; \u003C\/strong\u003EOverlap gap property: A topological barrier to optimizing over random structures\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u0026nbsp; \u003C\/strong\u003EMany decision and optimization problems over random structures exhibit a gap between the existential and algorithmically achievable values. Examples include the problem of finding a largest independent set in a random graph, the problem of finding a near ground state in a spin glass model, the problem of finding a satisfying assignment in a random constraint satisfaction problem, and many many more. At the same time, no formal computational hardness of these problems exists which would explain this persistent algorithmic gap.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIn the talk we will describe a new approach for establishing an algorithmic intractability for these problems called the overlap gap property. Originating in statistical physics, and specifically in the theory of spin glasses, this is a simple to describe property which a) emerges in most models known to exhibit an apparent algorithmic hardness; b) is consistent with the hardness\/tractability phase transition for many models analyzed to the day; and, importantly, c) allows to mathematically rigorously rule out a large class of algorithms as potential contenders, specifically the algorithms which exhibit the input stability (noise insensitivity).\u003C\/p\u003E\r\n\r\n\u003Cp\u003EWe will specifically show how to use this property to obtain stronger than the state of the art lower bounds on the depth of Boolean circuits for solving two of the aforementioned problems: the problem of finding a large independent set in a sparse random graph, and the problem of finding a near ground state of a p-spin model.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022http:\/\/www.mit.edu\/~gamarnik\/home.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@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":"Overlap gap property: A topological barrier to optimizing over random structures - Klaus 1116 at 11am"}],"uid":"27544","created_gmt":"2021-10-27 18:54:42","changed_gmt":"2022-02-01 16:34:48","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2022-02-14T11:00:00-05:00","event_time_end":"2022-02-14T12:00:00-05:00","event_time_end_last":"2022-02-14T12:00:00-05:00","gmt_time_start":"2022-02-14 16:00:00","gmt_time_end":"2022-02-14 17:00:00","gmt_time_end_last":"2022-02-14 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":""}}}