Nearly Optimal Sparse Group Testing

DOI10.1109/TIT.2019.2891651zbMATH Open1431.94213arXiv1708.03429OpenAlexW2908941128MaRDI QIDQ5223967FDOQ5223967

Authors: Venkata Gandikota, Elena Grigorescu, Sidharth Jaggi, Samson Zhou 

Publication date: 19 July 2019

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: Group testing is the process of pooling arbitrary subsets from a set of $n$ items so as to identify, with a minimal number of tests, a "small" subset of $d$ defective items. In "classical" non-adaptive group testing, it is known that when $d$ is substantially smaller than $n$, $Theta(dlog(n))$ tests are both information-theoretically necessary and sufficient to guarantee recovery with high probability. Group testing schemes in the literature meeting this bound require most items to be tested $Omega(log(n))$ times, and most tests to incorporate $Omega(n/d)$ items. Motivated by physical considerations, we study group testing models in which the testing procedure is constrained to be "sparse". Specifically, we consider (separately) scenarios in which (a) items are finitely divisible and hence may participate in at most $gammaino(log(n))$ tests; or (b) tests are size-constrained to pool no more than $hoino(n/d)$items per test. For both scenarios we provide information-theoretic lower bounds on the number of tests required to guarantee high probability recovery. In both scenarios we provide both randomized constructions (under both $epsilon$-error and zero-error reconstruction guarantees) and explicit constructions of designs with computationally efficient reconstruction algorithms that require a number of tests that are optimal up to constant or small polynomial factors in some regimes of $n,d,gamma,$ and $ho$. The randomized design/reconstruction algorithm in the $ho$-sized test scenario is universal -- independent of the value of $d$, as long as $hoino(n/d)$. We also investigate the effect of unreliability/noise in test outcomes. For the full abstract, please see the full text PDF.

Full work available at URL: https://arxiv.org/abs/1708.03429

Mathematics Subject Classification ID

Fault detection; testing in circuits and networks (94C12)

Cited In (8)

• Near-Optimal Sparsity-Constrained Group Testing: Improved Bounds and Algorithms
• A survey of cover-free families: constructions, applications, and generalizations
• Optimal Dorfman group testing for symmetric distributions
• Approximate message passing with rigorous guarantees for pooled data and quantitative group testing
• Real-valued group testing for quantitative molecular assays
• Information dissemination in wireless ad-hoc networks under the weighted-TIM framework
• Bounds and algorithms for generalized superimposed codes
• Sparse Combinatorial Group Testing

This page was built for publication: Nearly Optimal Sparse Group Testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5223967)