The following paper by Price and Scarlett appeared today on arXiv. It considers $k$ defective items, but given a fixed $p,$ one can choose $k=c p n,$ for example to have control over the probability of failure of this algorithm, via, say the Chernoff bound.

A Fast Binary Splitting Approach to Non-Adaptive Group Testing

From the 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^2 \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 $\Omega(n)$ storage, we also provide a low-storage variant based on hashing, with similar recovery guarantees.

The following paper by Price and Scarlett appeared today on arXiv. It considers $k$ defective items, but given a fixed $p,$ one can choose $k=c p n,$ for example to have control over the probability of failure of this algorithm, via, say the Chernoff bound.

Picking $c=2,$ for example would give probability of failure $P_{err}$ upper bounded by $$P_{err}\leq (e/4)^t\approx \frac{1}{1.47^t}$$ by the multiplicative Chernoff bound.

A Fast Binary Splitting Approach to Non-Adaptive Group Testing

From the 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^2 \log k · \log n)$ runtime previously available for any algorithm that only uses $O(k \log n)$ tests.

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 $\Omega(n)$ storage, we also provide a low-storage variant based on hashing, with similar recovery guarantees.