[edit]
A Non-Adaptive Algorithm for the Quantitative Group Testing Problem
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4574-4592, 2024.
Abstract
Consider an n-dimensional binary feature vector with k non-zero entries. The vector can be interpreted as the incident vector corresponding to n items out of which k items are \emph{defective}. The \emph{quantitative group testing} (QGT) problem aims at learning this binary feature vector by queries on subsets of the items that return the total number of defective items. We consider this problem under the \emph{non-adaptive} scenario where the queries on subsets are designed collectively and can be executed in parallel. Most of the existing efficient non-adaptive algorithms for the sublinear regime where k=nα with 0<α<1 fall short of the information-theoretic lower bound, with a multiplicative gap of logk. Recently, a near-optimal non-adaptive algorithm with a decoding complexity of O(n3) closed this gap. In this work, we present a concatenated construction method yielding a non-adaptive algorithm with a decoding complexity of O(n2α+nlog2n). The probability of decoding failure is analyzed by establishing a connection between the QGT problem and the so-called \emph{balls into bins} problem. Our algorithm reduces the gap between the information-theoretic and computational bound for the number of required queries/tests from logk to loglogk. This narrows the gap in the number of tests for non-adaptive algorithms within the class of algorithms with o(n2) decoding complexity. Moreover, although our algorithm exhibits a loglogk gap in terms of the number of tests, it is surpassed by the existing asymptotically optimal construction only in scenarios where k is exceptionally large for moderate values of α, such as k>1027 for α=0.7, thereby highlighting the practical applicability of our proposed concatenated construction.