Non-adaptive Quantitative Group Testing via Plotkin-Type Constructions

In this paper, we study the quantitative group testing problem, also known as the heavy hitter detection problem and the coin weighing problem, in a non-adaptive setting. In this problem, the aim is to recover k defective items from a group of n items with the smallest possible number of quantitative/additive tests, where each such test returns the number of defective items participating in the test. In the non-adaptive setting, that we study in this paper, all tests are designed at once and can be, in principle, run in parallel. We establish a novel construction method for designing non-adaptive test matrices with a nested structure inspired by the Plotkin concatenation in the coding theory literature. Our proposed algorithm identifies k defective items among the collection of n items with high probability using $k(1 + o(1))\log \left( {\frac{n}{k}} \right)$ non-adaptive tests in the sub-linear regime of k = o(n). Furthermore, our analysis demonstrates that the probability of decoding failure approaches zero exponentially in k as k, n → ∞. Our approach outperforms existing state-of-the-art methods for designing non-adaptive test schemes with efficient decoders for the quantitative group testing problem in terms of the required number of measurements.