ECCC-Report TR23-141https://eccc.weizmann.ac.il/report/2023/141Comments and Revisions published for TR23-141en-usWed, 20 Sep 2023 09:15:23 +0300
Paper TR23-141
| A Tight Lower Bound of $\Omega(\log n)$ for the Estimation of the Number of Defective Items |
Nader Bshouty,
Gergely Harcos
https://eccc.weizmann.ac.il/report/2023/141Let $X$ be a set of items of size $n$ , which may contain some defective items denoted by $I$, where $I \subseteq X$. In group testing, a {\it test} refers to a subset of items $Q \subset X$. The test outcome is $1$ (positive) if $Q$ contains at least one defective item, i.e., $Q\cap I \neq \emptyset$, and $0$ (negative) otherwise.
We give a novel approach to obtaining tight lower bounds in non-adaptive randomized group testing. Employing this new method, we can prove the following result.
Any non-adaptive randomized algorithm that, for any set of defective items $I$, with probability at least $2/3$, returns an estimate of the number of defective items $|I|$ to within a constant factor requires at least
$\Omega({\log n})$ tests.
Our result matches the upper bound of $O(\log n)$ and solves the open problem posed by Damaschke and Sheikh Muhammad.Wed, 20 Sep 2023 09:15:23 +0300https://eccc.weizmann.ac.il/report/2023/141