Group testing is the art of identifying a small number of "defective" items ($k$) within a massive population ($N$) by pooling samples into a smaller number of tests ($t$). Information theory tells us that if the defectives are rare, we can design non-adaptive testing matrices where the number of required tests scales optimally as $O(k \log N)$.
However, minimizing the number of tests introduces a severe computational bottleneck during the decoding phase. If a decoder must scan through every single one of the $N$ items to determine its status, the computational complexity scales linearly with the population size ($O(N)$). As Amin Emad points out in an analysis of semi-quantitative testing, linear-time scans fail to scale for massive genomic databases. To make large-scale screening practical, researchers have developed algorithms where decoding time scales with the number of tests or defectives, or logarithmically with the population size, bypassing the need to iterate through every individual item.
The Core Intuition: From Scanning to Elimination
How can we identify a needle in a haystack without looking at every piece of straw? The most straightforward sublinear decoding strategies rely on structured elimination. If we design a test matrix such that items appear in a carefully chosen subset of tests, a single negative test outcome instantly clears every item included in that pool.
As surveyed by Matthew Aldridge et al. in their monograph, combinatorial decoding identifies defectives by either eliminating individuals who appear in any negative test, or by isolating individuals who are the sole potential defectives in a positive test. To make this process computationally efficient, the underlying measurement matrix must possess specific combinatorial properties.
For instance, Ping Deng et al. demonstrate that structuring probe sets as $d$-disjunct matrices reduces the decoding process to a basic elimination procedure, avoiding the high-order polynomial complexity associated with weaker matrix designs Efficient non-unique probes selection algorithms for DNA microarray. Similarly, Jinping Fan et al. utilize strongly separable structures to ensure that increasing the efficiency of the test matrix does not create a computational bottleneck during the decoding phase Strongly separable matrices for nonadaptive combinatorial group testing. In mildly sublinear sparsity regimes, Larkin Flodin et al. show that this simple negative-elimination strategy provides a rigorous upper bound for exact recovery Probabilistic Group Testing with a Linear Number of Tests.
Direct Index Reconstruction via Bit-Checking
Elimination narrows down the candidates, but a more powerful mechanism embeds the binary indices of the items directly into the structure of the test matrix. Instead of asking "is this specific item defective?", the test outcomes themselves dictate the binary address of the defective items.
Population Items (N) ---> [ Structured Matrix Signatures ]
│
▼
Test Outcome Vector ---> [ Bit-Checking Decoder ] ──> Direct Logarithmic Recovery O(t log N)
Thach V. Bui et al. developed a deterministic framework where the decoding process is transformed into a bit-checking operation on the test outcome vector Efficient (nonrandom) Construction and Decoding for Non-adaptive Group Testing. By mapping the weight of specific segments in the test outcome vector directly to the binary indices of defective items, the authors shift the decoding complexity from being dependent on the total population size to being logarithmic relative to it, achieving a decoding speed of $O(t \log N)$.
This signature-embedding approach can be extended to complex environments where items interfere with one another. For instance, Thach V. Bui et al. applied structured signatures to group testing with inhibitors—where certain items mask the presence of defectives—reducing the computational complexity from linear to polylogarithmic relative to the total population size Sublinear decoding schemes for non-adaptive group testing with inhibitors.
Divide-and-Conquer: Splitting and Recursive Pruning
Another way to achieve sublinear decoding is to adapt sequential divide-and-conquer strategies (like binary search) into a non-adaptive, parallelizable format.
Eric Price et al. achieved this by parallelizing a classical sequential strategy into a fast binary splitting approach A Fast Binary Splitting Approach to Non-Adaptive Group Testing. Their algorithm slashes the decoding time down to $O(k \log N)$, matching the information-theoretic optimal test count and removing previous quadratic dependencies on the number of defectives. The authors later extended this technique to handle physical constraints, such as noisy outcomes and limited item participation, demonstrating that tree-based splitting structures maintain sublinear decoding speeds even under strict biological or physical limits on sample divisibility Fast Splitting Algorithms for Sparsity-Constrained and Noisy Group Testing.
Alternatively, one can decode recursively across layers of a matrix. Huseyin A. Inan et al. showed that the classic Kautz-Singleton construction can be decoded by identifying the bits of a defective item's index piece-by-piece On the Optimality of the Kautz-Singleton Construction in Probabilistic Group Testing. By pruning the search space across stacked matrix layers, the recursive process narrows the search to a small candidate set, making the decoding process exponentially faster for large populations.
Scaling Beyond Binary Channels
The push for sublinear decoding also spans non-binary testing models, such as threshold, quantitative, and semi-quantitative group testing, where tests provide more nuanced physical feedback than a simple yes/no.
In threshold group testing (where a pool is positive only if it contains at least a certain number of defectives), Thach V. Bui et al. leveraged efficient algorithms designed for classical disjunct matrices to achieve a decoding time of $t \times \text{poly}(d^2 \log N)$, which is sublinear in the total number of items Efficiently Decodable Non-Adaptive Threshold Group Testing. To eliminate the "gap" constraints common in threshold designs, Thach V. Bui et al. introduced a combinatorial tool called a "single selector" coupled with an exclusion-based decoding strategy, shifting the search space from exponential to polynomial scaling with the number of target items Efficient designs for threshold group testing without gap.
For quantitative setups, where the test returns a count of the defectives present, sublinear scaling is achieved by breaking the global problem apart. Mahdi Soleymani et al. introduced a concatenated matrix construction that decomposes the global identification problem into smaller, parallelizable sub-problems A Non-Adaptive Algorithm for the Quantitative Group Testing Problem. This reduces the computational overhead from cubic to nearly linear time.
Finally, in the semi-quantitative domain, Amin Emad established that decoding rare items from quantized pooled test results can be achieved with linear time complexity relative to the population size and the number of tests using SQ-disjunct codes Semi-Quantitative Group Testing, while Abhinav Ganesan et al. demonstrated threshold-based counting methods for populations containing inhibitors, scaling linearly with the total number of test observations rather than high-order polynomials Non-Adaptive Group Testing with Inhibitors.
Key Foundational Work
Efficient non-unique probes selection algorithms for DNA microarray (2008) — contributed 2 concept elements to this direction.
Semi-Quantitative Group Testing (2012) — contributed 1 concept elements to this direction.