2023/09/18 by Nader H. Bshouty, Bshouty, Nader H., Gergely Harcos +1
Medicine · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #HIV/AIDS drug development and treatment #SARS-CoV-2 detection and testing
paper · pdf · doi:10.48550/arxiv.2309.09613
openalex publication_date 2023/09/18 · openalex created_date 2023/09/20 · openalex updated_date 2026/07/28
Let X be a set of items of size n , which may contain some defective items denoted by I, where I ⊆ X. In group testing, a \it test refers to a subset of items Q ⊂ X. The test outcome is 1 (positive) if Q contains at least one defective item, i.e., Q∩ I ≠ ∅, and 0 (negative) otherwise. We give a novel approach to obtaining tight lower bounds in non-adaptive randomized group testing. Employing this new method, we can prove the following result. 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 Ω(log n) tests. Our result matches the upper bound of O(log n) and solves the open problem posed by Damaschke and Sheikh Muhammad.