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 ⊆ X be the set of defective items. A group test is a subset Q ⊆ X of items. The result of the test Q with respect to I is defined by Q(I) := 1 if Q ∩ I = ∅ 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 [14, 19, 27] .
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, 13, [23] [24] [25] . 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 [2, 3, 5, 7, 9, 10, 12, 21] . The target in some of these papers is to find an estimationd within an additive factor of ǫ < 1 such that (1 − ǫ)d ≤d ≤ (1 + ǫ)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/ǫ 2 log 1/δ) queries in expectation where δ is the failure probability of the algorithm. Bshouty et. al. [3] modified this result and gave an algorithm that uses (1 − δ) log log d + O((1/ǫ 2 ) log 1/δ) expected number of queries. Moreover, they proved a lower bound of (1 − δ) log log d + Ω((1/ǫ) log(1/δ)) 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/δ)) log n) tests and in [2] , Bshouty gives the lower bound Ω(log n/ log log n).
In this paper, we are interested in d eterministic adaptive and non-adaptive algorithms that estimate the defective items set size d up to a multiplicative factor of ∆ > 1. Formally, let |I| := d and let D ≥ d. We say that a deterministic algorithm A estimates d up to a multiplicative factor of ∆ if, given D as an input to the algorithm, it evaluates an estimationd such that d/∆ ≤d ≤ d∆. 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 Ω(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 Ω((D/∆ 2 ) log(n/D)) queries for any non-adaptive deterministic algorithm. Moreover, using a non-constructive proof, they give an upper bound of O (((log D)/(log ∆))D log n) 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 ∆ must make at least Ω (D/∆ 2 ) log(n/D) 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/∆ 2 ) (log(n/D) + log ∆)) by means of non-constructive proof. This improves the lower bound O((log D)/(log ∆))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) /∆ 2 ) · log n) tests, and the second makes (D/∆ 2 ) · 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, · · · , n} be a set of items. Let I ⊆ 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 ⊆ 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 ∩ I = ∅ and 0 otherwise. We denote by OI an oracle that for a test Q returns Q(I).
Let A be an algorithm with an access to OI , and let d = |I|. We say that the algorithm A estimates d up to a multiplicative factor of ∆, if A gets as an input an upper bound D ≥ d and a parameter ∆ > 1, and outputsd such that d/∆ ≤d ≤ d∆. We say that 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 ≥ ∆ 2 , otherwise, the algorithm trivially outputsd = D/∆. We note here that ∆ ≥ 1 + Ω(1), that is, it is greater than a constant that is greater than 1 and it may depend 2 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 ∆ = 1 + o(n) where o() (small o) is with respect to D and/or n.
We will use the following 
In particular,
(2)
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 ∆. We prove:
tests and outputsd such that d ∆ ≤d ≤ d∆. To prove the Theorem we need the following:
There is a non-adaptive deterministic algorithm that makes
1. If the number of defectives d is less than ℓ/∆ 2 , it outputs 0.
Therefore, such c exists and we have 1/2 ≤ c ≤ 2. Consider a test Q ⊆ [n] chosen at random where each item i ∈ [n] is chosen to be in Q with probability ∆ 2 /(cℓ). Let I be the set of defective items such that |I| = d, and let Q(I) be the result of the test Q with respect to the set I. Then,
and if d = ℓ/∆, we get:
Let Q1, Q2, . . . , Qt be a sequence of t i.i.d tests such that
where c ′ = 54e 2 and c ′′ = 4e. Let
Consider the following two events:
A: There is a set of defectives I of size |I| ≤ ℓ/∆ 2 such that the number of tests with 0 answer is less than ηt.
There is a set of defectives J of size |J| > ℓ/∆ such that the number of tests with 0 answer is at least ηt.
Notice that, to prove the lemma it is enough to prove that Pr[A ∨ B] < 1. We will show that
. . , Xt be random variables such that Xi = 1 if and only if Qi(I) = 0. Let X be the number of tests that yield the result 0. Therefore,
By (3) in Lemma 1, for λ = 1/2 − 1/(2∆) we have
Using this result, equations (4) and the union bound, we can conclude that
On the other hand, for the event B, we have two cases.
If there is a set of defectives J of size |J| > ℓ/∆ such that more than ηt of the tests yield the answer 0, then there is a set of defectives J ′ of size |J ′ | = ℓ/∆ such that more than ηt of the tests answers are 0. Denote by B ′ the latter event. Then, by (8) 
If 1 < ∆ ≤ 2 then 0 ≤ λ ≤ 1 and then by (1) in Lemma 1, we have
In this case we have ℓ/∆ > 2ℓ/∆ 2 . Therefore, if there is a set of defectives J of size |J| > ℓ/∆ such that more than ηt of the tests yield the answer 0, then there is a set of defectives J ′ of size |J ′ | = 2ℓ/∆ 2 such that more than ηt of the tests answers are 0. Denote by B ′′ the latter event. By (7), µ = E[X] = e −2 t. Let λ = 1/3 − 1/(3∆) < 1. Then ηt > (1 + λ)µ. By (1) in Lemma 1, we have
Then
We are now ready to prove Theorem 2.
Let A(ℓ, ∆) be the algorithm from Lemma 3. Then, A(ℓ, ∆) makes at most
queries for some constant c, and Let q = ⌈log D/ log ∆⌉. Let t denote the number of queries performed by algorithm T (n, D, ∆). By (10) , the number of tests is at most 
In this section, we prove the following lower bound.
Theorem 5. Any deterministic adaptive group testing algorithm that given D > d, outputsd that satisfies d/∆ ≤d ≤ ∆d must make at least
For the proof, we use the following from [3] . there is a test Q ⊆ [n] that is asked by A that gives answer 0 to I and 1 to I ′ . Since I ′ ∩ Q = ∅, there is a subset J ′ ∈ J such that J ′ ∩ Q = ∅ and therefore Q gives answer 1 to J ′ . Then s(J ′ ) = s(I) and we get a contradiction. Since s(I ′ ) = s(I) and algorithm A outputs 0 to I, it also outputs 0 to I ′ . Therefore, |I ′ | ≤ d2. Therefore |J | ≤ N := d 2 d 1 . That is, for every possible sequence of answers s ′ of the algorithm A, there is at most N sets of size d1 that get the same sequence of answers. Since there are L := n d 1 such sets, the number of different sequences of answers that A might have must be at least L/N . By Lemma 6, the number of tests that the algorithm makes is at least
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.
Proof. Let d1 = D/∆ 2 − 1 and d2 = D. For sets of size less than or equal d1 the algorithm returns d1/∆ ≤d ≤ ∆d1 and for sets of equal to d2 the algorithm returns d2/∆ <d ≤ ∆d2. Since ∆d1 < d2/∆, the above intervals are disjoint. So, the algorithm can distinguish between sets of size less that or equal to d1 and sets of size greater than d2. By Lemma 7 the algorithm must make at least Ω D ∆ 2 log n D tests.
In this section, we prove: tests and outputsd such that d ∆ ≤d ≤ d∆. 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 Q1 and Q2. The algorithm asks the queries defined by Q1 and Q2 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/∆ 2 distinct defective sets, it continues to split and test. Two cases can happen. Either it gets D/∆ 2 defective sets and then the algorithm outputsd = D/∆, or the number of the defective sets is always less than D/∆ 2 and then, the algorithm finds all the defective items and returns their exact number. The algorithm is given in Figure 2 Lemma 9. Algorithm Adaptive-dEstimate is a deterministic adaptive algorithm that makes
tests and outputs an estimationd such that: Proof. If d ≤ D ∆ 2 , then the splitting process in step 2 of the algorithm proceeds until each defective item belongs to a distinct set. Eventually, the condition in step 2.2 is met and the algorithm outputs the exact value of d. If d > D/∆ 2 , then the splitting process stops when the number of defective sets |Q| exceeds D/∆ 2 . The algorithm halts and outputsd = |Q|∆. Obviously, |Q| ≤ d. Therefore,d = |Q|∆ ≤ d∆.
The number of iterations cannot exceed log n iterations. In the first log(D/∆ 2 ) iterations, in the worst case scenario, the algorithm splits its current set Qi on each iteration into two sets Q i (I) = 1. Therefore, the number of tests that the algorithm asks over all the first log(D/∆ 2 ) iterations is at most
Since |Q| ≤ D/∆ 2 , in the other log n − log(D/∆ 2 ) iterations, the algorithm makes at most 2D/∆ 2 tests each iteration. So, the total number of tests is at most
In this section, we show how to use expanders, condensers and extractors to construct deterministic non-adaptive algorithms for defectives number estimation. We prove: 1. If |I| < ak/δ, then A outputs 0.
2. If |I| ≥ k, then A outputs 1.
Proof. For every j ∈ R, we define the test T (j) = {i|(i, j) ∈ E}. The number of tests is |R| = m. If |I| ≥ k, then |Γ(I)| ≥ ak. Therefore, at least ak tests will give positive answer 1. If |I| < ak/δ, then, since the degree of every vertex in L is δ, we have |Γ(I)| ≤ δ|I| < ak. This shows that, for this case, at most ak − 1 tests give the answer 1. Hence, we can distinguish between the two cases.
Following the same proof of Lemma 4 with algorithm T in Figure 1 , we have:
Lemma 12. Let A(ℓ, ∆) be a deterministic non-adaptive algorithm such that, for n items, it makes m(ℓ, ∆) tests and satisfies:
1. If |I| < ℓ/∆ 2 , then A outputs 0.
Then, there is a deterministic non-adaptive algorithm T such that, given D > d, for n items it makes
tests and outputsd that satisfies d/∆ ≤d ≤ ∆d.
The parameters of the explicit construction of a (k, a)-expander δ-regular bipartite graph from [4] are summarised in the following lemma.
Lemma 13. For any k > 0 and 0 < ǫ < 1, there is an explicit construction of a (k, a)-expander δ-regular bipartite graph with m = O(kδ/ǫ), δ = 2 O(log 3 (log n/ǫ)) , a = (1 − ǫ)δ.
We now prove:
There is a polynomial time deterministic non-adaptive algorithm that makes
tests and outputsd that satisfies d ∆ ≤d ≤ ∆d.
Proof. We use the expander in Lemma 13. Recall that ∆ = 1 + Ω(1). Let r = min(∆, 2), ǫ = 1 − 1/r and k = rℓ/∆ 2 . Then a = δ/r = 2 O(log 3 log n) and m = m(ℓ, ∆) = (ℓ/∆ 2 )2 O(log 3 log n) . By Lemma 11, there is a deterministic non-adaptive algorithm A such that for n items, it makes m(ℓ, ∆) tests and 1. If |I| < ak/δ = ℓ/∆ 2 then A outputs 0.
2. If |I| ≥ k = rℓ/∆ 2 then A outputs 1.
Algorithm A trivially satisfies the first condition required by Lemma 12. Consider item 2. If ∆ < 2 then r = ∆ and then if |I| ≥ k = ℓ/∆ then A outputs 1. If ∆ > 2 then r = 2 and then if |I| ≥ k = 2ℓ/∆ 2 then A outputs 1. Since 2ℓ/∆ 2 < ℓ/∆, if |I| ≥ ℓ/∆ then A outputs 1. Now by Lemma 12, there is a deterministic non-adaptive algorithm T such that, given D > d, for n items, it makes
tests and outputsd that satisfies d/∆ ≤d ≤ ∆d.
Extractors are functions that convert weak random sources into almost-perfect random sources. We use these objects to construct a non-adaptive algorithm for estimating d. We start with some definitions.
Definition 15. Let X be a random variable over a finite set S. We say that X has min-entropy at
Definition 16. Let X and Y be random variables over a finite set S. We say that X and
We denote by U ℓ the uniform distribution on {0, 1} ℓ . The notations Prx∈B or Ex∈B stand for the fact that the probability and the expectation are taken when x is chosen randomly uniformly from B. Definition 18. Let Σ be a finite set. An n-mixture over Σ is an n−tuple S := (S1, · · · , Sn) such that for all i ∈ [n], Si ⊆ Σ.
Using these definitions and notations, we restate the result proved by Cheraghchi [6] (Theorem 9) in the following lemma. . The rows of the matrix T are indexed byT ×M . Let T (i) denote the ith column of T . Therefore, for r ∈T and j ∈M , the row (r, j) in the matrix T is denoted by T (r,j) . Moreover, the ith entry of the row T (r,j) is denoted by T (r,j),i and T (r,j),i = T (i) (r,j) = 1 if and only if Mr,i = j. The size of the test matrix T is m × n.
Let the defective elements be si 1 , . . . , si ℓ and let y ∈ {0, 1} m indicate the tests result. Then, y is equal to T (s i 1 ) ∨ · · · ∨ T (s i ℓ ) . Let S = (Sr) r∈T be a 2t−mixture over {0, 1}m where for all r ∈T ,
(r,j) = 1}. It is easy to see that: 1. |Sr| ≤ ℓ. This is because, by the definition of Sr, j ∈ Sr if and only if y (r,j) = 1. The entry y (r,j) gets the value 1 if at least one of the entries T (s i 1 ) (r,j) , · · · , T (s i ℓ ) (r,j) is 1. Any row in T (s i 1 ) , · · · , T (s i ℓ ) has exactly one entry that is equal to 1 in all the 2m rows indexed by r. Hence, each row can cause one item to be inserted to Sr. If the number of defectives is less than (1 − ǫ)2 k ′ then, by Lemma 19, all columns, except for at most 2 k columns, satisfy
So for less than 2 k + 1 columns we have Pr r∈T [M Proof. We use the notations from Lemma 21. Let C = 27 · 2 c−2 . We choose ǫ = 2/3 and k ′ such that (1 − ǫ)2 k ′ = ℓ/∆ 2 . Then 2 k = 2 k ′ +2 log(1/ǫ)+c = 27 · 2 c−2 ℓ ∆ 2 < ℓ ∆ By Lemma 20, there is a deterministic non-adaptive algorithm A for n = 2n items that makes m = 2t +m =n2 O(log k log(k/ǫ)) ℓ (1 − ǫ)∆ 2 = 2 log 2 log(ℓ/∆) ℓ ∆ 2 log n tests that satisfies the following:
1. If the number of defectives is less than (1 − ǫ)2 k ′ = ℓ/∆ 2 then A outputs 0.
2. If the number of defectives is greater than or equal 2 k + 1 then A outputs 1 and, since 2 k < ℓ/∆, in particular, if the number of defectives is greater than or equal ℓ/∆ then A outputs 1.
By Lemma 12, the result follows.
A similar work by Capalbo et.al. [4] gives an explicit constrction of a lossless condenser is summarised in the following lemma:
Lemma 23. For all positive integersn, k and all ǫ > 0, there is an explicit lossless condenser F : {0, 1}n × {0, 1}t → {0, 1}m witht = O(log 3 (n/ǫ)) andm = k + log(1/ǫ) + O(1).
The construction from Lemma 23 yields a result that is similar to the one established in Lemma 22. 