Optimal Deterministic Group Testing Algorithms
to Estimate the Number of Defectives

The problem of group testing is the problem of identifying or, in some cases, examining the properties of a small amount of items known as defective items within a pile of elements using group tests. Let $X$ be a set of $n$ items, and let $I\subseteq X$ be the set of defective items. A group test is a subset $Q\subseteq X$ of items. The result of the test $Q$ with respect to $I$ is defined by $Q(I):=1$ if $Q\cap I\neq\emptyset$ and $Q(I):=0$ otherwise. While the defective set $I$ is unknown to the algorithm, in many cases we might be interested in finding the size of the defective set $|I|$, or at least an estimation of that value with a minimum number of tests.

Group testing was originally proposed as a potential solution for economising mass blood testing during WWII [11]. Since then, group testing approach has been diversely applied in a wide area of practical applications including DNA library screening [20], product testing quality control[22], file searching in storage systems [17], sequential screening of experimental variables [18], efficient contention algorithms for MAC [17, 26], data compression [16], and computations in data stream model [8]. Recently, during the COVID-19 pandemic outbreak, a number of researches adopted the group testing paradigm not only to accelerate mass testing process, but also to dramatically reduce the number of kits required for testing due to severe shortages in the testing kits supply [27, 14, 19].

While an up-front knowledge of the value of $d$ or at least an upper bound on it is required in many of the algorithms aimed at identifying the defective items, estimating or finding the number of defectives is an interesting problem on its own as well. Defectives estimation via group testing has been applied vastly in biological and medical applications [7, 23, 24, 25, 13]. In [24], for example, group testing algorithms are used to estimate aster-yellow virus transmitters proportion over the organisms in a natural population of leafhoppers. Similarly, in [25], the authors estimate the infection rate of the yellow-fever virus in mosquito population using group testing methods. On the other hand, in [13], group-testing-based estimation of rare diseases prevalence is employed not only for its effectiveness but also because it naturally preserves individual anonymity of the subjects.

Algorithms dedicated for this task might operate in stages or rounds. In each round, the tests are defined in advance and tested in a single parallel step. Tests on some round might depend on the test results of the preceding rounds. A single round algorithm is called non-adaptive algorithm, while a multi-round algorithm is called adaptive algorithm.

In recent years, there has been an increasing interest in the problem of estimating the number of defective items via group testing[3, 2, 7, 5, 9, 10, 12, 21]. The target in some of these papers is to find an estimation $\hat{d}$ within an additive factor of $\epsilon<1$ such that $(1-\epsilon)d\leq\hat{d}\leq(1+\epsilon)d$. For randomized adaptive algorithms we have the following results. Falhatgar et.al. [12] give a randomised adaptive algorithm that estimates $d$ using $2\log\log d+O(1/\epsilon^{2}\log 1/\delta)$ queries in expectation where $\delta$ is the failure probability of the algorithm. Bshouty et. al. [3] modified this result and gave an algorithm that uses $(1-\delta)\log\log d+O((1/\epsilon^{2})\log 1/\delta)$ expected number of queries. Moreover, they proved a lower bound of $(1-\delta)\log\log d+\Omega((1/\epsilon)\log(1/\delta))$ queries.

For randomized non-adaptive algorithms with constant estimation, Damaschke and Sheikh Muhammad give in [10] a randomized non-adaptive algorithm that makes $O((\log(1/\delta))\log n)$ tests and in [2], Bshouty gives the lower bound $\Omega(\log n/\log\log n)$.

In this paper, we are interested in deterministic adaptive and non-adaptive algorithms that estimate the defective items set size $d$ up to a multiplicative factor of $\Delta>1$. Formally, let $|I|:=d$ and let $D\geq d$. We say that a deterministic algorithm $\cal A$ estimates $d$ up to a multiplicative factor of $\Delta$ if, given $D$ as an input to the algorithm, it evaluates an estimation $\hat{d}$ such that $d/\Delta\leq\hat{d}\leq d\Delta$. Bshouty et al. show in [3] that, if no upper bound $D$ is given to the algorithm, then any deterministic adaptive algorithm (and therefore also non-deterministic algorithm) for this problem must make at least $\Omega(n)$ tests. This is equivalent to testing all the items. This justifies the fact that any non-trivial efficient algorithm must have some upper bound $D$ for $d$.

Agarwal et.al.  [1] consider this problem. They first give the lower bound of $\Omega((D/\Delta^{2})$ $\log({n}/{D}))$ queries for any non-adaptive deterministic algorithm. Moreover, using a non-constructive proof, they give an upper bound of $O\left((({\log D})/({\log\Delta}))D\log n\right)$ queries.

We further investigate this problem. We bring new lower and upper bounds on the number of tests required both in adaptive and non-adaptive deterministic algorithms. 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 [1] for non-adaptive algorithms. Furthermore, we give a polynomial time adaptive algorithm that shows that our bound is tight up to a small additive term.

For non-adaptive algorithms, we achieve an upper bound of $O((D/\Delta^{2})$ $(\log(n/D)+\log\Delta))$ by means of non-constructive proof. This improves the lower bound $O((\log D)/(\log\Delta))D\log n)$ from [1], and matches the lower bound up to a small additive term.

We then study polynomial time constructive algorithms. For this task, we use existing polynomial time constructible expander regular bipartite graphs, extractors and 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. To the best of our knowledge, this is the first explicit construction with an almost optimal test complexity. Our results are summarised in Table 1.

In this section, we give some notations and definition that will be used in this paper.

Let $X=[n]:=\{1,\cdots,n\}$ be a set of items. Let $I\subseteq X$ be a set of defective items, and let $d$ denote its size, i.e. $d=|I|$. In the group testing settings, a test is a subset $Q\subseteq X$ of items. An answer to a test $Q$ with respect to the defective items set $I$, is denoted by $Q(I)$, such that $Q(I):=1$ if $Q\cap I\neq\emptyset$ and $0$ otherwise. We denote by ${\cal O}_{I}$ an oracle that for a test $Q$ returns $Q(I)$.

Let ${\cal A}$ be an algorithm with an access to ${\cal O}_{I}$, and let $d=|I|$. We say that the algorithm ${\cal A}$ estimates $d$ up to a multiplicative factor of $\Delta$, if ${\cal A}$ gets as an input an upper bound $D\geq d$ and a parameter $\Delta>1$, and outputs $\hat{d}$ such that $d/\Delta\leq\hat{d}\leq d\Delta$. We say that ${\cal A}$ is an adaptive algorithm, if its queries depend on the result of previous queries, and non-adaptive if its queries are independent of previous ones and therefore, can be executed in a single parallel step. We may assume that $D\geq\Delta^{2}$, otherwise, the algorithm trivially outputs $\hat{d}=D/\Delta$. We note here that $\Delta\geq 1+\Omega(1)$, that is, it is greater than a constant that is greater than $1$ and it may depend²²2For example $\Delta=\log\log n+\log D$ on $n$ and/or $D$. This is implicit in [1] and is also constrained in this paper. It is also interesting to investigate this problem when $\Delta=1+o(n)$ where $o()$ (small $o$) is with respect to $D$ and/or $n$.

We will use the following

Moreover, we will often use the inequality

In this section, we give the upper bound for deterministic non-adaptive algorithm that estimates $d$ up to a multiplicative factor of $\Delta$. We prove:

To prove the Theorem we need the following:

We are now ready to prove Theorem 2.

Let ${\cal A}(\ell,\Delta)$ be the algorithm from Lemma 3. Then, ${\cal A}(\ell,\Delta)$ makes at most

queries for some constant $c$, and

1. 1.

   If ${\cal A}(\ell,\Delta)=1$, then $d\geq\frac{\ell}{\Delta^{2}}$.

2. 2.

   If ${\cal A}(\ell,\Delta)=0$, then $d\leq\frac{\ell}{\Delta}.$

Consider the algorithm ${\cal T}(n,D,\Delta)$ that runs ${\cal A}(D/\Delta^{i},\Delta)$ for all $i=0,\ldots,\lceil\log D/\log\Delta\rceil$. Let $r$ be the minimum integer such that ${\cal A}(D/\Delta^{r},\Delta)=1$. Algorithm ${\cal T}(n,D,\Delta)$ then outputs $\hat{d}=D/\Delta^{r+1}$. See algorithm ${\cal T}$ in Figure 1.

We now prove:

In this section, we prove the following lower bound.

For the proof, we use the following from [3].

The following Lemma assists us to prove the result declared by Theorem 5.

The conclusions established by Lemma 7 show that the upper bound from Lemma  3 is tight. Moreover, using these results, we provide the following proof for Theorem 5.

In this section, we prove:

We first describe the algorithm. The algorithm gets as an input the set of items $X=[n]$ and splits it into two equally-sized disjoint sets $Q_{1}$ and $Q_{2}$. The algorithm asks the queries defined by $Q_{1}$ and $Q_{2}$ and proceeds in the splitting process on the sets that yielded positive answers only. We call these sets defective sets. As long as the algorithm gets less than $D/\Delta^{2}$ distinct defective sets, it continues to split and test. Two cases can happen. Either it gets $D/\Delta^{2}$ defective sets and then the algorithm outputs $\hat{d}=D/\Delta$, or the number of the defective sets is always less than $D/\Delta^{2}$ and then, the algorithm finds all the defective items and returns their exact number. The algorithm is given in Figure 2. The algorithm invokes the procedure ${\bf Split}(X)$ that on an input $X=\{a_{1},a_{2},\ldots,a_{n}\}$, it returns the set $W$ where $W:=\{X_{1},X_{2}\}$ such that $X_{i}\subseteq X$, $X_{1}=\{a_{1},a_{2},\ldots,a_{\left\lfloor{n/2}\right\rfloor}\}$, $X_{2}=\{a_{\left\lfloor{n/2}\right\rfloor+1},\ldots,a_{n}\}$ if $|X|\geq 2$, and $W:=\{X\}$ otherwise.

In this section, we show how to use expanders, condensers and extractors to construct deterministic non-adaptive algorithms for defectives number estimation. We prove: