Non-Adaptive Randomized Algorithm for Group Testing

Nader H. Bshouty, Nuha Diab, Shada R. Kawar, Robert J. Shahla
Proceedings of the 28th International Conference on Algorithmic Learning Theory, PMLR 76:109-128, 2017.

Abstract

We study the problem of group testing with a non-adaptive randomized algorithm in the random incidence design (RID) model where each entry in the test is chosen randomly independently from $\{0,1\}$ with a fixed probability $p$.

The property that is sufficient and necessary for a unique decoding is the separability of the tests, but unfortunately no linear time algorithm is known for such tests. In order to achieve linear-time decodable tests, the algorithms in the literature use the disjunction property that gives almost optimal number of tests.

We define a new property for the tests which we call semi-disjunction property. We show that there is a linear time decoding for such test and for $d\to \infty$ the number of tests converges to the number of tests with the separability property. Our analysis shows that, in the RID model, the number of tests in our algorithm is better than the one with the disjunction property even for small $d$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v76-bshouty17a, title = {Non-Adaptive Randomized Algorithm for Group Testing}, author = {Bshouty, Nader H. and Diab, Nuha and Kawar, Shada R. and Shahla, Robert J.}, booktitle = {Proceedings of the 28th International Conference on Algorithmic Learning Theory}, pages = {109--128}, year = {2017}, editor = {Hanneke, Steve and Reyzin, Lev}, volume = {76}, series = {Proceedings of Machine Learning Research}, month = {15--17 Oct}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v76/bshouty17a/bshouty17a.pdf}, url = {https://proceedings.mlr.press/v76/bshouty17a.html}, abstract = {We study the problem of group testing with a non-adaptive randomized algorithm in the random incidence design (RID) model where each entry in the test is chosen randomly independently from $\{0,1\}$ with a fixed probability $p$.

The property that is sufficient and necessary for a unique decoding is the separability of the tests, but unfortunately no linear time algorithm is known for such tests. In order to achieve linear-time decodable tests, the algorithms in the literature use the disjunction property that gives almost optimal number of tests.

We define a new property for the tests which we call semi-disjunction property. We show that there is a linear time decoding for such test and for $d\to \infty$ the number of tests converges to the number of tests with the separability property. Our analysis shows that, in the RID model, the number of tests in our algorithm is better than the one with the disjunction property even for small $d$.} }
Endnote
%0 Conference Paper %T Non-Adaptive Randomized Algorithm for Group Testing %A Nader H. Bshouty %A Nuha Diab %A Shada R. Kawar %A Robert J. Shahla %B Proceedings of the 28th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2017 %E Steve Hanneke %E Lev Reyzin %F pmlr-v76-bshouty17a %I PMLR %P 109--128 %U https://proceedings.mlr.press/v76/bshouty17a.html %V 76 %X We study the problem of group testing with a non-adaptive randomized algorithm in the random incidence design (RID) model where each entry in the test is chosen randomly independently from $\{0,1\}$ with a fixed probability $p$.

The property that is sufficient and necessary for a unique decoding is the separability of the tests, but unfortunately no linear time algorithm is known for such tests. In order to achieve linear-time decodable tests, the algorithms in the literature use the disjunction property that gives almost optimal number of tests.

We define a new property for the tests which we call semi-disjunction property. We show that there is a linear time decoding for such test and for $d\to \infty$ the number of tests converges to the number of tests with the separability property. Our analysis shows that, in the RID model, the number of tests in our algorithm is better than the one with the disjunction property even for small $d$.
APA
Bshouty, N.H., Diab, N., Kawar, S.R. & Shahla, R.J.. (2017). Non-Adaptive Randomized Algorithm for Group Testing. Proceedings of the 28th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 76:109-128 Available from https://proceedings.mlr.press/v76/bshouty17a.html.

Related Material