Statistical and Computational Phase Transitions in Group Testing
We study the group testing problem where the goal is to identify a set of k
infected individuals carrying a rare disease within a population of size n,
based on the outcomes of pooled tests which return positive whenever there is
at least one infected individual in the tested group. We consider two different
simple random procedures for assigning individuals to tests: the
constant-column design and Bernoulli design. Our first set of results concerns
the fundamental statistical limits. For the constant-column design, we give a
new information-theoretic lower bound which implies that the proportion of
correctly identifiable infected individuals undergoes a sharp "all-or-nothing"
phase transition when the number of tests crosses a particular threshold. For
the Bernoulli design, we determine the precise number of tests required to
solve the associated detection problem (where the goal is to distinguish
between a group testing instance and pure noise), improving both the upper and
lower bounds of Truong, Aldridge, and Scarlett (2020). For both group testing
models, we also study the power of computationally efficient (polynomial-time)
inference procedures. We determine the precise number of tests required for the
class of low-degree polynomial algorithms to solve the detection problem. This
provides evidence for an inherent computational-statistical gap in both the
detection and recovery problems at small sparsity levels. Notably, our evidence
is contrary to that of Iliopoulos and Zadik (2021), who predicted the absence
of a computational-statistical gap in the Bernoulli design.