ECCC-Report TR18-053https://eccc.weizmann.ac.il/report/2018/053Comments and Revisions published for TR18-053en-usMon, 19 Mar 2018 14:44:21 +0200
Paper TR18-053
| Lower Bound for Non-Adaptive Estimate the Number of Defective Items |
Nader Bshouty
https://eccc.weizmann.ac.il/report/2018/053We 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.Mon, 19 Mar 2018 14:44:21 +0200https://eccc.weizmann.ac.il/report/2018/053