*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Algorithms & Randomness Center (ARC)
Alex Wein (Georgia Tech)
Monday, February 28, 2022
Klaus 1116 - 11:00 am
Title: Statistical and Computational Phase Transitions on Group Testing
Abstract: 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?
I will tell the story of a few different frameworks that have been used to understand these questions. Based on a "first moment overlap gap property" 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 "low-degree polynomial algorithms" 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.
Based on joint work with Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, and Ilias Zadik.
---------------------------------------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
