In the group testing problem one aims to infer a small set of k infected individuals out of a large population of size n. At our disposal we have a testing scheme which allows us to test a group of individuals, such that the outcome of the test is positive, if and only if at least one infected individual is part of the test. All tests are carried out in parallel. The overall goal is to find a test design and an inference algorithm requiring as few tests as possible, such that the infected individuals can be identified with high probability. As most relevant during the outbreak of pandemic diseases (Wang et al.,2011), our analysis focusses on the so-called sublinear regime of group testing, where k \sim n^\theta. The optimal group testing schemes require a test-size of \sim n/k and each individual has to take part in\sim \log n tests (Coja-Oghlan et. al, 2019). In real world applications, like testing many individuals in a short period of time during the outbreak of epidemics, pooling in such a way is not possible due to dilution effects. Evidence of those effects is known for important applications like HIV (Wein, 1996) or COVID-19 (Seifried and Ciesek, 2020). Our main contribution is the analysis of a group testing model, where we restrict the individuals-per-test to be finite. We present an easy to implement scheme to pool individuals into tests under these natural restrictions coming with the efficient decoding algorithm DD and present simulations which suggest that the decoding procedure succeeds for moderate population sizes. Furthermore, we show that our pooling schemerequires the fewest tests as possible under all pooling schemes (with \theta \in (0,1)), with n individuals among which k are infected. However, the required number of tests may increase substantially under real-world practical constraints, notably including bounds on the maximum number \Delta of tests an individual can be placed in, or the maximum number \Gamma of individuals in a given test. While previous works have given recovery guarantees for these settings, significant gaps remain between the achievability and converse bounds. In this paper, we substantially or completely close several of the most prominent gaps. In the case of \Delta-divisible items, we show that the definite defectives (DD) algorithm coupled with a random regular design is asymptotically optimal in dense scaling regimes, and optimal to within a factor of e more generally; we establish this by strengthening both the best known achievability and converse bounds. In the case of \Gamma-sized tests, we provide a comprehensive analysis of the regime \Gamma = \Theta(1), and again establish a precise threshold proving the asymptotic optimality of DD equipped with a tailored pooling scheme} . Finally, we apply our methods to the finitely many tests-per-individuals setting, where we provide a full understanding of the random regular test-design in this model by building up on work of (Gandikota et al., 2016) .
Recent advances in noiseless non-adaptive group testing have led to a precise asymptotic characterization of the number of tests required for high-probability recovery in the sublinear regime k = n^{\theta (with \theta \in (0,1)), with n individuals among which k are infected. However, the required number of tests may increase substantially under real-world practical constraints, notably including bounds on the maximum number \Delta of tests an individual can be placed in, or the maximum number \Gamma of individuals in a given test. While previous works have given recovery guarantees for these settings, significant gaps remain between the achievability and converse bounds. In this paper, we substantially or completely close several of the most prominent gaps. In the case of \Delta-divisible items, we show that the definite defectives (DD) algorithm coupled with a random regular design is asymptotically optimal in dense scaling regimes, and optimal to within a factor of e more generally; we establish this by strengthening both the best known achievability and converse bounds. In the case of \Gamma-sized tests, we provide a comprehensive analysis of the regime \Gamma = \Theta(1), and again establish a precise threshold proving the asymptotic optimality of DD equipped with a tailored pooling scheme} . Finally, for each of these two settings, we provide near-optimal adaptive algorithms based on sequential splitting, and provably demonstrate gaps between the performance of optimal adaptive and non-adaptive algorithms .
R
In the group testing problem one aims to infer a small set of k infected individuals out of a large population of size n. At our disposal we have a testing scheme which allows us to test a group of individuals, such that the outcome of the test is positive, if and only if at least one infected individual is part of the test. All tests are carried out in parallel. The overall goal is to find a test design and an inference algorithm requiring as few tests as possible, such that the infected individuals can be identified with high probability. As most relevant during the outbreak of pandemic diseases (Wang et al.,2011), our analysis focusses on the so-called sublinear regime of group testing, where k \sim n^\theta. The optimal group testing schemes require a test-size of \sim n/k and each individual has to take part in\sim \log n tests (Coja-Oghlan et. al, 2019). In real world applications, like testing many individuals in a short period of time during the outbreak of epidemics, pooling in such a way is not possible due to dilution effects. Evidence of those effects is known for important applications like HIV (Wein, 1996) or COVID-19 (Seifried and Ciesek, 2020). Our main contribution is the analysis of a group testing model, where we restrict the individuals-per-test to be finite. We present an easy to implement scheme to pool individuals into tests under these natural restrictions coming with the efficient decoding algorithm DD and present simulations which suggest that the decoding procedure succeeds for moderate population sizes. Furthermore, we show that our pooling schemerequires the fewest tests as possible under all pooling schemes
Recent advances in noiseless non-adaptive group testing have led to a precise asymptotic characterization of the number of tests required for high-probability recovery in the sublinear regime k = n^{\theta
R
we apply our methods to the finitely many tests-per-individuals setting, where we provide a full understanding of the random regular test-design in this model by building up on work of (Gandikota et al., 2016)
for each of these two settings, we provide near-optimal adaptive algorithms based on sequential splitting, and provably demonstrate gaps between the performance of optimal adaptive and non-adaptive algorithms