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

Abstract

In Group Testing, the objective is to identify $K$ defective items out of $N$, $K\ll 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 $\ddot{I}$ proportion of false positives (the $\ddot{I}$-False Positive Channel), where $\ddot{I}$ is a constant, with asymptotically-optimal number of tests and decoding complexity, i.e. $\mathcal{O}(K\log 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~\cite{price2023fast} in two ways: First, under $\ddot{I}$-proportion of test results flipped ($\ddot{I}$-Binary Symmetric Channel) and within the general sublinear regime $K=\hat{I}˜(N^{\hat{I}}\pm )$ where $0<\hat{I}\pm <1$, our algorithm has a decoding complexity of $\mathcal{O}(\hat{I}{\mu }^{-2}{K}^{1+\hat{I}\mu })$ where $\hat{I}\mu >0$ is a constant parameter. Second, when the false negative flipping probability $\ddot{I}{}^{\prime }$ satisfies $\ddot{I}{}^{\prime }=\mathcal{O}(K^{-\hat{I}\mu })$ and the false positive flipping probability $\ddot{I}$ is a constant, we can simultaneously achieve $\mathcal{O}(\hat{I}{\mu }^{-1}K\log N)$ for both the number of tests and the decoding complexity. It remains open to achieve these optimals under the general BSC.