  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
\cdot \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.
