Near-Optimal Sparsity-Constrained Group Testing: Improved Bounds and Algorithms

DOI10.1109/TIT.2022.3141244MaRDI QIDQ5088467zbMATH OpenOpenAlexFDO

Authors Oliver Gebhard, Max Hahn-Klimroth, Manuel Penschuck, Maurice Rolvien, Jonathan Scarlett, Nelvin Tan, O. Parczyk

Publication date 13 July 2022

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

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

zbMATH Keywords

definite defectives (DD) algorithmrandom regular designsparsity-constrained group testing

Mathematics Subject Classification ID

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

Abstract: Recent advances in noiseless non-adaptive group testing have led to a precise asymptotic characterization of the number of tests required for high-probability recovery in the sublinear regime $k=n^{heta}$ (with $hetain(0,1)$), with $n$ individuals among which $k$ are infected. However, the required number of tests may increase substantially under real-world practical constraints, notably including bounds on the maximum number $Delta$ of tests an individual can be placed in, or the maximum number $Gamma$ of individuals in a given test. While previous works have given recovery guarantees for these settings, significant gaps remain between the achievability and converse bounds. In this paper, we substantially or completely close several of the most prominent gaps. In the case of $Delta$-divisible items, we show that the definite defectives (DD) algorithm coupled with a random regular design is asymptotically optimal in dense scaling regimes, and optimal to within a factor of $eul$ more generally; we establish this by strengthening both the best known achievability and converse bounds. In the case of $Gamma$-sized tests, we provide a comprehensive analysis of the regime $Gamma=Theta(1)$, and again establish a precise threshold proving the asymptotic optimality of SCOMP (a slight refinement of DD) equipped with a tailored pooling scheme. Finally, for each of these two settings, we provide near-optimal adaptive algorithms based on sequential splitting, and provably demonstrate gaps between the performance of optimal adaptive and non-adaptive algorithms.

Recommendations

• Nearly Optimal Sparse Group Testing
• Optimal non-adaptive probabilistic group testing in general sparsity regimes
• Fast splitting algorithms for sparsity-constrained and noisy group testing
• Sparse Combinatorial Group Testing
• Group Testing Algorithms: Bounds and Simulations
• Non-Adaptive Group Testing: Explicit Bounds and Novel Algorithms
• Nonadaptive Group Testing Based on Sparse Pooling Graphs
• An optimal group testing algorithm on \(k\) disjoint sets
• A tight upper bound for group testing in graphs
• On optimal nested group testing algorithms

Cited in

(5)

• Real-valued group testing for quantitative molecular assays
• Sparse Combinatorial Group Testing
• Approximate message passing with rigorous guarantees for pooled data and quantitative group testing
• Interactive aggregate message authentication equipped with detecting functionality from adaptive group testing
• Twenty questions with random error

This page was built for publication: Near-Optimal Sparsity-Constrained Group Testing: Improved Bounds and Algorithms

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