Noisy Group Testing in the Linear Regime: Exact Thresholds and Efficient

Lukas Hintze, Lena Krieg, Olga Scheftelowitsch, Haodong Zhu
Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:2805-2821, 2025.

Abstract

In group testing, the task is to identify defective items by testing groups of them together using as few tests as possible. We consider the setting where each item is defective with a constant probability $\alpha$, independent of all other items. In the (over-)idealized noiseless setting, tests are positive exactly if any of the tested items are defective. We study a more realistic model in which observed test results are subject to noise, i.e., tests can display false positive or false negative results with constant positive probabilities. We determine precise constants $c$ such that $cn\log n$ tests are required to recover the infection status of every individual for both adaptive and non-adaptive group testing: in the former, the selection of groups to test can depend on previously observed test results, whereas it cannot in the latter. Additionally, for both settings, we provide efficient algorithms that identify all defective items with the optimal amount of tests with high probability. Thus, we completely solve the problem of binary noisy group testing in the studied setting.

Cite this Paper

BibTeX
@InProceedings{pmlr-v291-hintze25a, title = {Noisy Group Testing in the Linear Regime: Exact Thresholds and Efficient }, author = {Hintze, Lukas and Krieg, Lena and Scheftelowitsch, Olga and Zhu, Haodong}, booktitle = {Proceedings of Thirty Eighth Conference on Learning Theory}, pages = {2805--2821}, year = {2025}, editor = {Haghtalab, Nika and Moitra, Ankur}, volume = {291}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--04 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v291/main/assets/hintze25a/hintze25a.pdf}, url = {https://proceedings.mlr.press/v291/hintze25a.html}, abstract = {In group testing, the task is to identify defective items by testing groups of them together using as few tests as possible. We consider the setting where each item is defective with a constant probability $\alpha$, independent of all other items. In the (over-)idealized noiseless setting, tests are positive exactly if any of the tested items are defective. We study a more realistic model in which observed test results are subject to noise, i.e., tests can display false positive or false negative results with constant positive probabilities. We determine precise constants $c$ such that $cn\log n$ tests are required to recover the infection status of every individual for both adaptive and non-adaptive group testing: in the former, the selection of groups to test can depend on previously observed test results, whereas it cannot in the latter. Additionally, for both settings, we provide efficient algorithms that identify all defective items with the optimal amount of tests with high probability. Thus, we completely solve the problem of binary noisy group testing in the studied setting.} }
Endnote
%0 Conference Paper %T Noisy Group Testing in the Linear Regime: Exact Thresholds and Efficient %A Lukas Hintze %A Lena Krieg %A Olga Scheftelowitsch %A Haodong Zhu %B Proceedings of Thirty Eighth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2025 %E Nika Haghtalab %E Ankur Moitra %F pmlr-v291-hintze25a %I PMLR %P 2805--2821 %U https://proceedings.mlr.press/v291/hintze25a.html %V 291 %X In group testing, the task is to identify defective items by testing groups of them together using as few tests as possible. We consider the setting where each item is defective with a constant probability $\alpha$, independent of all other items. In the (over-)idealized noiseless setting, tests are positive exactly if any of the tested items are defective. We study a more realistic model in which observed test results are subject to noise, i.e., tests can display false positive or false negative results with constant positive probabilities. We determine precise constants $c$ such that $cn\log n$ tests are required to recover the infection status of every individual for both adaptive and non-adaptive group testing: in the former, the selection of groups to test can depend on previously observed test results, whereas it cannot in the latter. Additionally, for both settings, we provide efficient algorithms that identify all defective items with the optimal amount of tests with high probability. Thus, we completely solve the problem of binary noisy group testing in the studied setting.
APA
Hintze, L., Krieg, L., Scheftelowitsch, O. & Zhu, H.. (2025). Noisy Group Testing in the Linear Regime: Exact Thresholds and Efficient . Proceedings of Thirty Eighth Conference on Learning Theory, in Proceedings of Machine Learning Research 291:2805-2821 Available from https://proceedings.mlr.press/v291/hintze25a.html.

Related Material