On the All-Or-Nothing Behavior of Bernoulli Group Testing
share
In this paper, we study the problem of group testing, in which one seeks to identify which items are defective given a set of suitably-designed tests whose outcomes indicate whether or not at least one defective item was included in the test. The most widespread recovery criterion seeks to exactly recovery the entire defective set, and relaxed criteria such as approximate recovery and list decoding have also been considered. In this paper, we study the fundamental limits of group testing under two significantly relaxed criteria: The weak detection criterion only seeks to distinguish (with high probability) between whether the outcomes were produced according to the group testing model or independently from the test design, and the weak recovery criterion only seeks to identify a small fraction (e.g., 0.01) of the defective items. In the case of Bernoulli random testing, we identify scenarios in which an all-or-nothing phenomenon occurs: When the number of tests is slightly below a threshold, weak detection and weak recovery are impossible, whereas when the number of tests is slightly above the same threshold, high-probability exact recovery is possible. Our impossibility results significantly strengthen existing ones that only hold for stricter recovery criteria.
READ FULL TEXT