A Tight Scale-Locality Bound for Partial Detection in Non-Adaptive Group Testing

Abstract

We give a lower bound for randomized non-adaptive group testing when the goal is to find any $\ell$ defective items but the total number $d$ of defectives is unknown. Bshouty and Haddad-Zaknoon proved an upper bound of $O(\ell {\log }^{2}n)$ tests and a lower bound of $$\Omega \left(\frac{\ell {\log }^{2}n}{\log \ell +\log \log n}\right).$$ We prove the matching lower bound. More generally, we show that every randomized non-adaptive algorithm that succeeds with constant probability for every defective set must use $$\Omega \left(\ell {\log }^2(n/\ell )\right)$$ tests. The proof is as follows. At a fixed value of $d$, finding $\ell$ defectives requires about $\ell \log (n/d)$ bits of information. On the other hand, one fixed group test is informative only when its size is tuned to the scale of $d$; across all logarithmic scales of $d$, a single test contributes only $O(1)$ bits. Summing over all scales gives the lower bound. We also record the matching upper bound $$O\left(\ell {\log }^2(n/\ell )\right),$$ obtained by running the known-$d$ algorithm in parallel over dyadic guesses for $d$. Thus the randomized non-adaptive complexity of unknown-$d$ partial detection is $\Theta \left(\ell {\log }^2(n/\ell )\right)$ for constant success probability.