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
