Optimal deterministic group testing algorithms to estimate the number of defectives

In this work, we study the problem of estimating the number of defectives d in a set of n items up to a multiplicative factor of Delta > 1 using deterministic group testing algorithms. Particularly, given A > 1 and D > d, we give upper and lower bounds on the number of tests required for the task of generating an estimation (d) over cap such that d/Delta < <(d)over cap>< dA. In the adaptive settings, we prove that any adaptive deterministic algorithm for estimating d must perform at least Omega(2)((D/Delta(2)) log(n/D)) tests. This extends the same lower bound achieved in [1] for non-adaptive algorithms. In addition, we show that our bound is tight up to a small additive term by constructing an adaptive algorithm for this task. Furthermore, we give a non-constructive proof of an upper bound of O ((D/Delta(2)) (log(n/D) + log A)) for the non-adaptive settings. This bound is an improvement over the upper bound O ((log D)/(log A))D log n) from [1], and matches the lower bound up to a small additive term. Moreover, we use existing techniques for building expander regular bipartite graphs, extractors and condensers from [2,3] to construct two polynomial-time non-adaptive algorithms for estimating d. Using the construction from [2], a polynomial non-adaptive algorithm that makes O ((D1+o(1)/A2) & middot; log n) tests are defined. The second algorithm exploits the construction from [3] to build another non-adaptive algorithm that performs (D/Delta(2)) . Q uazipoly (log n) tests. This is the first explicit construction with an almost optimal test complexity. (C) 2021 Elsevier B.V. All rights reserved.