Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > NON-ADAPTIVE LEARNING:
Reports tagged with Non-adaptive Learning:
TR18-053 | 19th March 2018
Nader Bshouty

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

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.

more >>>

ISSN 1433-8092 | Imprint