2023/08/15 by Nader H. Bshouty, Bshouty, Nader H.
Medicine · #SARS-CoV-2 detection and testing
paper · pdf · doi:10.48550/arxiv.2308.07721
Let X be a set of items of size n that contains some defective items, denoted by I, where I ⊆ X. In group testing, a \it test refers to a subset of items Q ⊂ X. The outcome of a test is 1 if Q contains at least one defective item, i.e., Q∩ I ≠ ∅, and 0 otherwise. We give a novel approach to obtaining lower bounds in non-adaptive randomized group testing. The technique produced lower bounds that are within a factor of 1/loglog\stackrelk⋯log n of the existing upper bounds for any constant~k. Employing this new method, we can prove the following result. For any fixed constants k, 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 Ω(\fraclog nloglog\stackrelk⋯log n) tests. Our result almost matches the upper bound of O(log n) and solves the open problem posed by Damaschke and Sheikh Muhammad [COCOA 2010 and Discrete Math., Alg. and Appl., 2010]. Additionally, it improves upon the lower bound of Ω(log n/loglog n) previously established by Bshouty [ISAAC 2019].