Optimal Deterministic Group Testing Algorithms to Estimate the Number of Defectives

Abstract

We study the problem of estimating the number of defective items $d$ within a pile of $n$ elements up to a multiplicative factor of $\Delta >1$, using deterministic group testing algorithms. We bring lower and upper bounds on the number of tests required in both the adaptive and the non-adaptive deterministic settings given an upper bound $D$ on the defectives number. For the adaptive deterministic settings, our results show that, any algorithm for estimating the defectives number up to a multiplicative factor of $\Delta$ must make at least $\Omega \left((D/{\Delta }^2)\log (n/D)\right)$ tests. This extends the same lower bound achieved in \cite{ALA17} for non-adaptive algorithms. Moreover, we give a polynomial time adaptive algorithm that shows that our bound is tight up to a small additive term. For non-adaptive algorithms, an upper bound of $O((D/{\Delta }^2)$ $(\log (n/D)+\log \Delta ))$ is achieved by means of non-constructive proof. This improves the lower bound $O((\log D)/(\log \Delta ))D\log n)$ from \cite{ALA17} and matches the lower bound up to a small additive term. In addition, we study polynomial time constructive algorithms. We use existing polynomial time constructible \emph{expander regular bipartite graphs}, \emph{extractors} and \emph{condensers} to construct two polynomial time algorithms. The first algorithm makes $O((D^{1+o(1)}/{\Delta }^2)\cdot \log n)$ tests, and the second makes $(D/{\Delta }^2)\cdot quazipoly$ $(\log n)$ tests. This is the first explicit construction with an almost optimal test complexity.