# Noisy Nonadaptive Group Testing with Binary Splitting: New Test Design and Improvement on Price-Scarlett-Tan's Scheme

arXiv: https://arxiv.org/abs/2410.14566 · HTML: https://mlsanity.com/paper/2410.14566/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Oct 2024.

## Built on by (most cited first, 3 of 3)

- [A Fast Binary Splitting Approach for Non-Adaptive Learning of ErdHos--R'enyi Graphs](https://mlsanity.com/paper/2511.17240/) (2025)
- [Efficient Support Recovery of Mixtures of Sparse Linear Classifiers with Fewer Measurements](https://mlsanity.com/paper/2609.32176/) (2026)
- [Non-Adaptive Learning of Sparse ErdHos--R'enyi Graphs via Affine Splitting](https://mlsanity.com/paper/2609.33704/) (2026)

## Abstract (arXiv)

In Group Testing, the objective is to identify K defective items out of N, Kll N, by testing pools of items together and using the least amount of tests possible. Recently, a fast decoding method based on binary splitting (Price and Scarlett, 2020) has been proposed that simultaneously achieve optimal number of tests and decoding complexity for Non-Adaptive Probabilistic Group Testing (NAPGT). However, the method works only when the test results are noiseless. In this paper, we further study the binary splitting method and propose (1) A NAPGT scheme that generalizes the original binary splitting method from the noiseless case into tests with ρ proportion of false positives (the ρ-False Positive Channel), where ρ is a constant, with asymptotically-optimal number of tests and decoding complexity, i.e. O(Klog N), and (2) A NAPGT scheme in the presence of both false positives and false negatives in test outcomes, improving and generalizing the work of Price, Scarlett and Tan~citeprice2023fast in two ways: First, under ρ-proportion of test results flipped (ρ-Binary Symmetric Channel) and within the general sublinear regime K=Theta(Nα) where 0<α<1, our algorithm has a decoding complexity of O(ε-2K1+ε) where ε>0 is a constant parameter. Second, when the false negative flipping probability ρ' satisfies ρ'=O(K-ε) and the false positive flipping probability ρ is a constant, we can simultaneously achieve O(ε-1Klog N) for both the number of tests and the decoding complexity. It remains open to achieve these optimals under the general BSC.