Near-Optimal Sparse Adaptive Group Testing
share
In group testing, the goal is to identify a subset of defective items within a larger set of items based on tests whose outcomes indicate whether any defective item is present. This problem is relevant in areas such as medical testing, data science, communications, and many more. Motivated by physical considerations, we consider a sparsity-based constrained setting (Gandikota et al., 2019), in which items are finitely divisible and thus may participate in at most γ tests (or alternatively, each test may contain at most ρ items). While information-theoretic limits and algorithms are known for the non-adaptive setting, relatively little is known in the adaptive setting. In this paper, we address this gap by providing an information-theoretic converse that holds even in the adaptive setting, as well as a near-optimal noiseless adaptive algorithm. In broad scaling regimes, our upper and lower bounds on the number of tests asymptotically match up to a factor of e.
READ FULL TEXT