A Non-Adaptive Algorithm for the Quantitative Group Testing Problem

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^\alpha$ with $0 < \alpha < 1$ fall short of the information-theoretic lower bound, with a multiplicative gap of $\log k$. Recently, a near-optimal non-adaptive algorithm with a decoding complexity of $O(n^3)$ closed this gap. In this work, we present a concatenated construction method yielding a non-adaptive algorithm with a decoding complexity of $O(n^{2\alpha} + n \log^2 n)$. 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 $\log k$ to $\log \log k$. This narrows the gap in the number of tests for non-adaptive algorithms within the class of algorithms with $o(n^2)$ decoding complexity. Moreover, although our algorithm exhibits a $\log \log k$ 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 $\alpha$, such as $k > 10^{27}$ for $\alpha = 0.7$, thereby highlighting the practical applicability of our proposed concatenated construction.