Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR18-053 | 19th March 2018 12:39

Lower Bound for Non-Adaptive Estimate the Number of Defective Items

RSS-Feed




TR18-053
Authors: Nader Bshouty
Publication: 19th March 2018 14:44
Downloads: 201
Keywords: 


Abstract:

We prove that to estimate within a constant factor the number of defective items in a non-adaptive group testing algorithm we need at least $\tilde\Omega((\log n)(\log(1/\delta)))$ tests. This solves the open problem posed by Damaschke and Sheikh Muhammad.



ISSN 1433-8092 | Imprint