{"655642":{"#nid":"655642","#data":{"type":"event","title":" ARC Colloquium: Alex Wein  (Georgia Tech)","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\u003E\u0026nbsp; Alex Wein\u0026nbsp; (Georgia Tech)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, February 28, 2022\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 - 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:\u003C\/strong\u003E\u0026nbsp;\u003Cstrong\u003E\u0026nbsp;\u003C\/strong\u003EStatistical and Computational Phase Transitions on Group Testing\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u0026nbsp; In the group testing problem, the goal is to identify a set of k infected individuals carrying a rare disease within a population of size n, based on pooled tests which pick a random subset of individuals and return positive iff at least one of them is infected. This is a problem of practical importance, and also a good testbed for exploring statistical-computational gaps: How many tests are needed in order to infer the infected individuals from the test results? And how many tests are needed to do so in a computationally-efficient manner?\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nI will tell the story of a few different frameworks that have been used to understand these questions. Based on a \u0026quot;first moment overlap gap property\u0026quot; calculation and numerical simulations, it was conjectured (but not proven) that a Markov chain Monte Carlo (MCMC) method achieves poly-time reconstruction with the information-theoretically optimal number of tests, that is, there is no statistical-computational gap (Iliopoulos and Zadik, 2020). However, our new results provide contrary evidence: we prove that the class of \u0026quot;low-degree polynomial algorithms\u0026quot; cannot reach the information-theoretic threshold; this suggests that there *is* an inherent stat-comp gap, although we do not formally rule out the MCMC algorithm of [IZ20]. I will discuss some new tools for proving low-degree lower bounds, and give an overview of some of the mysteries and open problems that remain.\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nBased on joint work with Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, and Ilias Zadik.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E---------------------------------------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/www.alex-wein.com\/\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":"Statistical and Computational Phase Transitions in Group Testing - Klaus 1116 at 11am"}],"uid":"36162","created_gmt":"2022-02-21 19:00:07","changed_gmt":"2022-02-22 14:04:20","author":"apillai32","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2022-02-28T11:00:00-05:00","event_time_end":"2022-02-28T12:00:00-05:00","event_time_end_last":"2022-02-28T12:00:00-05:00","gmt_time_start":"2022-02-28 16:00:00","gmt_time_end":"2022-02-28 17:00:00","gmt_time_end_last":"2022-02-28 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":""}}}