A Fast Binary Splitting Approach to Non-Adaptive Group Testing

Eric Price, Jonathan Scarlett

TL;DR

This paper introduces a non-adaptive group testing algorithm that identifies $k$ defective items out of $n$ using an information-theoretically optimal $O(k \log n)$ tests while simultaneously slashing the decoding runtime down to $O(k \log n)$. By porting the intuition of classical adaptive binary splitting into an upfront, non-adaptive tree design, the authors reduce the decoding runtime’s dependence on $k$ from quadratic ($O(k^2 \log k \log n)$) to strictly linear.

What Problem Does This Paper Address?

In group testing, the objective is to pinpoint a small subset of $k$ defective (or infected) items among a huge population of $n$ items ($k \ll n$). Each test pools together a subset of items and returns a binary outcome: $1$ if at least one item in the pool is defective, and $0$ otherwise.

In non-adaptive group testing, all pooling designs must be fixed in advance—allowing tests to be run in parallel. When operating under the standard probabilistic ("for-each") recovery guarantee:

  • The information-theoretic lower bound mandates $\Omega(k \log n)$ tests.
  • Achieving this optimal test bound historically required either linear-in-$n$ decoding time ($\Omega(n)$) or quadratic-in-$k$ decoding time (such as Bit-Mixing Coding at $O(k^2 \log k \cdot \log n)$).
  • Faster algorithms (like SAFFRON) incurred a penalty in sample complexity, requiring $O(k \log k \log n)$ tests.

The open challenge was whether an algorithm could simultaneously achieve both optimal $O(k \log n)$ sample complexity and fast, near-linear $O(k \log n)$ sublinear decoding time.

Methods

The authors build on Hwang’s celebrated adaptive binary splitting algorithm (1972), which recursively cuts candidate groups in half to isolate defectives. To eliminate adaptivity, the authors run the entire tree's tests non-adaptively in parallel:

  1. Dyadic Group Tree: Items are grouped into a binary tree of depth $\log_2 n$. Testing begins at level $\ell_{\min} = \log_2 k$ (since higher levels are almost guaranteed to test positive and convey little information).
  2. Non-Adaptive Level Tests: At each level $\ell$ from $\log_2 k$ to $\log_2 n - 1$, each of the $2^\ell$ item groups is mapped uniformly at random into one of $Ck$ tests.
  3. Top-Down Filtering: Decoding proceeds top-down. At each level, any group assigned to a negative test is discarded along with its entire subtree (because in noiseless testing, no defective item can ever produce a negative test outcome). If a group's test is positive, both of its children are flagged as "possibly defective" and passed to the next level.
  4. Final Disambiguation: Singletons that survive to the leaf level ($\ell = \log_2 n$) are run through $C' \log k$ independent batches of $2k$ tests to filter out remaining false-positive non-defectives.
  5. Low-Storage Hashing: To avoid explicitly storing $\Omega(n)$ random test assignments, the authors replace full randomness with $O(\log k)$-wise independent hash families (e.g., Wegman–Carter polynomials over finite fields) combined with $\widetilde{C}$ repetitions per level.

Datasets

Not discussed in the paper. The work is strictly theoretical, providing formal mathematical proofs of performance bounds within the word-RAM model of computation.

Key Insights and Ideas

  • Simulating Adaptivity via Branching Extinction: Although the test matrix is fixed up front, the decoder traverses the tree dynamically. Because at most $k$ tests at any level can be positive, any given non-defective group has at most a $1/C$ chance of colliding with a defective item. For $C \ge 16$, the exploration of non-defective subtrees behaves like a subcritical Galton–Watson branching process that rapidly goes extinct.
  • $O(k)$ Leaves Without Multi-Stage Clean-Up: A rigorous path tail bound demonstrates that despite potential overlaps across subtrees, the number of surviving non-defective candidate leaves is bounded by $O(k)$ with overwhelming probability ($1 - e^{-\Omega(k)}$). This circumvents the need for multi-stage bucketing used in concurrent works.
  • Taming Covariance with Limited Independence: By bounding the inclusion-exclusion expansion up to degree $\Theta(\log k)$, the authors show that low-degree independence is sufficient to maintain a conditional variance of $O(k)$ for the number of false-positive candidates at each level.

Key Results

  • Optimal Tests & Linear-in-$k$ Decoding Time:
  • Total tests: $t = O(k \log n)$.
  • Decoding runtime: $O(k \log n)$ operations in the word-RAM model.
  • Success probability: $1 - O(k^{-c})$ for any constant $c > 0$.
  • Baseline storage: $O(n \log^2 k)$ bits.
  • Sublinear Storage Variant:
  • Using Wegman–Carter hash functions, storage drops from linear in $n$ to $O(k \log n + \log k \log^2 n)$ bits (drastically sublinear when $k \ll n$).
  • Runtime with hashing: $O(k \log k \log n)$.
  • Success probability: $1 - O\left(\frac{\log n}{k^c}\right)$.
Metric BMC [Bondorf et al., 2019] SAFFRON [Lee et al., 2019] This Paper
Number of Tests $O(k \log n)$ $O(k \log k \log n)$ $O(k \log n)$
Decoding Time $O(k^2 \log k \log n)$ $O(k \log k)$ (word-RAM) $O(k \log n)$
Recovery Guarantee For-each For-each For-each

Limitations and Future Work

  • Noiseless Assumption: The algorithm critically relies on the absence of false negatives. A single false negative at an early level prunes an entire branch of true defectives. Extending the tree traversal to handle false negative noise without substantial runtime penalties remains an open challenge.
  • Error Floor for Small $k$ in Low-Storage Regime: In the hash-based low-storage version, error probability scales as $1 - O\left(\frac{\log n}{k^c}\right)$, requiring $k = (\log n)^{\Omega(1)}$ to guarantee asymptotically vanishing error.
  • Independence Requirements: The low-storage version relies on $\Theta(\log k)$-wise independence; whether similar recovery guarantees can be proven under $O(1)$-wise independence is left as an open question.

Summary updated

Abstract

In this paper, we consider the problem of noiseless non-adaptive group testing under the for-each recovery guarantee, also known as probabilistic group testing. In the case of n items and k defectives, we provide an algorithm attaining high-probability recovery with O(k log n) scaling in both the number of tests and runtime, improving on the best known O(k² log k ⋅ log n) runtime previously available for any algorithm that only uses O(k log n) tests. Our algorithm bears resemblance to Hwang’s adaptive generalized binary splitting algorithm (Hwang, 1972); we recursively work with groups of items of geometrically vanishing sizes, while maintaining a list of "possibly defective" groups and circumventing the need for adaptivity. While the most basic form of our algorithm requires Ω(n) storage, we also provide a low-storage variant based on hashing, with similar recovery guarantees.
BibTeX
@inproceedings{price2020fast,
  author = {Eric Price and Jonathan Scarlett},
  title = {{A Fast Binary Splitting Approach to Non-Adaptive Group Testing}},
  booktitle = {APPROX-RANDOM},
  year = {2020},
  url = {https://openreview.net/forum?id=SaMNMxj1Pgc},
}

Loading related content...

Figure