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∼nθ infected individuals out of a population size n, 0<θ<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 minf, 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