  The group testing problem consists of determining a small set of defective
items from a larger set of items based on a number of possibly-noisy tests, and
is relevant in applications such as medical testing, communication protocols,
pattern matching, and more. We study the noisy version of this problem, where
the outcome of each standard noiseless group test is subject to independent
noise, corresponding to passing the noiseless result through a binary channel.
We introduce a class of algorithms that we refer to as Near-Definite Defectives
(NDD), and study bounds on the required number of tests for asymptotically
vanishing error probability under Bernoulli random test designs. In addition,
we study algorithm-independent converse results, giving lower bounds on the
required number of tests under Bernoulli test designs. Under reverse Z-channel
noise, the achievable rates and converse results match in a broad range of
sparsity regimes, and under Z-channel noise, the two match in a narrower range
of dense/low-noise regimes. We observe that although these two channels have
the same Shannon capacity when viewed as a communication channel, they can
behave quite differently when it comes to group testing. Finally, we extend our
analysis of these noise models to a general binary noise model (including
symmetric noise), and show improvements over known existing bounds in broad
scaling regimes.
