Optimal Group Testing

Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Philipp Loick
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1374-1388, 2020.

Abstract

In the group testing problem, which goes back to the work of Dorfman (1943), we aim to identify a small set of $k\sim n^\theta$ infected individuals out of a population size $n$, $0<\theta<1$.We avail ourselves to a test procedure that can test a group of individuals, with the test returning a positive result iff at least one individual in the group is infected. All tests are conducted in parallel. The aim is to devise a test design with as few tests as possible so that the infected individuals can be identified with high probability. We establish an explicit sharp information-theoretic/algorithmic phase transition $m_{inf}$, showing that with more than $\minf$ tests the infected individuals can be identified in polynomial time, while this is impossible with fewer tests. In addition, we obtain an optimal two-stage adaptive group testing scheme. These results resolve problems prominently posed in [Aldridge et al. 2019, Johnson et al. 2018, Mézard and Toninelli 2011].

Cite this Paper

BibTeX
@InProceedings{pmlr-v125-coja-oghlan20a, title = {Optimal Group Testing}, author = {Coja-Oghlan, Amin and Gebhard, Oliver and Hahn-Klimroth, Max and Loick, Philipp}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {1374--1388}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/coja-oghlan20a/coja-oghlan20a.pdf}, url = {https://proceedings.mlr.press/v125/coja-oghlan20a.html}, abstract = { In the group testing problem, which goes back to the work of Dorfman (1943), we aim to identify a small set of $k\sim n^\theta$ infected individuals out of a population size $n$, $0<\theta<1$.We avail ourselves to a test procedure that can test a group of individuals, with the test returning a positive result iff at least one individual in the group is infected. All tests are conducted in parallel. The aim is to devise a test design with as few tests as possible so that the infected individuals can be identified with high probability. We establish an explicit sharp information-theoretic/algorithmic phase transition $m_{inf}$, showing that with more than $\minf$ tests the infected individuals can be identified in polynomial time, while this is impossible with fewer tests. In addition, we obtain an optimal two-stage adaptive group testing scheme. These results resolve problems prominently posed in [Aldridge et al. 2019, Johnson et al. 2018, Mézard and Toninelli 2011].} }
Endnote
%0 Conference Paper %T Optimal Group Testing %A Amin Coja-Oghlan %A Oliver Gebhard %A Max Hahn-Klimroth %A Philipp Loick %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-coja-oghlan20a %I PMLR %P 1374--1388 %U https://proceedings.mlr.press/v125/coja-oghlan20a.html %V 125 %X In the group testing problem, which goes back to the work of Dorfman (1943), we aim to identify a small set of $k\sim n^\theta$ infected individuals out of a population size $n$, $0<\theta<1$.We avail ourselves to a test procedure that can test a group of individuals, with the test returning a positive result iff at least one individual in the group is infected. All tests are conducted in parallel. The aim is to devise a test design with as few tests as possible so that the infected individuals can be identified with high probability. We establish an explicit sharp information-theoretic/algorithmic phase transition $m_{inf}$, showing that with more than $\minf$ tests the infected individuals can be identified in polynomial time, while this is impossible with fewer tests. In addition, we obtain an optimal two-stage adaptive group testing scheme. These results resolve problems prominently posed in [Aldridge et al. 2019, Johnson et al. 2018, Mézard and Toninelli 2011].
APA
Coja-Oghlan, A., Gebhard, O., Hahn-Klimroth, M. & Loick, P.. (2020). Optimal Group Testing. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:1374-1388 Available from https://proceedings.mlr.press/v125/coja-oghlan20a.html.

Related Material