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

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.