Document Open Access Logo

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

Author Nader H. Bshouty

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2019.2.pdf
  • Filesize: 438 kB
  • 9 pages

Document Identifiers

Author Details

Nader H. Bshouty
  • Department of Computer Science, Technion, Haifa, Israel

Cite As Get BibTex

Nader H. Bshouty. Lower Bound for Non-Adaptive Estimation of the Number of Defective Items. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 2:1-2:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ISAAC.2019.2

Abstract

We prove that to estimate within a constant factor the number of defective items in a non-adaptive randomized group testing algorithm we need at least Omega~(log n) tests. This solves the open problem posed by Damaschke and Sheikh Muhammad in [Peter Damaschke and Azam Sheikh Muhammad, 2010; Peter Damaschke and Azam Sheikh Muhammad, 2010].

Subject Classification

ACM Subject Classification
  • Mathematics of computing
  • Mathematics of computing → Discrete mathematics
  • Mathematics of computing → Probabilistic algorithms
  • Theory of computation → Probabilistic computation
Keywords
  • Group Testing
  • Estimation
  • Defective Items

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Nader H. Bshouty, Vivian E. Bshouty-Hurani, George Haddad, Thomas Hashem, Fadi Khoury, and Omar Sharafy. Adaptive Group Testing Algorithms to Estimate the Number of Defectives. ALT, 2017. URL: http://arxiv.org/abs/1712.00615.
  2. Chao L. Chen and William H. Swallow. Using Group Testing to Estimate a Proportion, and to Test the Binomial Model. Biometrics., 46(4):1035-1046, 1990. Google Scholar
  3. Yongxi Cheng and Yinfeng Xu. An efficient FPRAS type group testing procedure to approximate the number of defectives. J. Comb. Optim., 27(2):302-314, 2014. URL: https://doi.org/10.1007/s10878-012-9516-5.
  4. Ferdinando Cicalese. Fault-Tolerant Search Algorithms - Reliable Computation with Unreliable Information. Monographs in Theoretical Computer Science. An EATCS Series. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-17327-1.
  5. Graham Cormode and S. Muthukrishnan. What’s hot and what’s not: tracking most frequent items dynamically. ACM Trans. Database Syst., 30(1):249-278, 2005. URL: https://doi.org/10.1145/1061318.1061325.
  6. Peter Damaschke and Azam Sheikh Muhammad. Bounds for Nonadaptive Group Tests to Estimate the Amount of Defectives. In Combinatorial Optimization and Applications - 4th International Conference, COCOA 2010, Kailua-Kona, HI, USA, December 18-20, 2010, Proceedings, Part II, pages 117-130, 2010. URL: https://doi.org/10.1007/978-3-642-17461-2_10.
  7. Peter Damaschke and Azam Sheikh Muhammad. Competitive Group Testing and Learning Hidden Vertex Covers with Minimum Adaptivity. Discrete Math., Alg. and Appl., 2(3):291-312, 2010. URL: https://doi.org/10.1142/S179383091000067X.
  8. R. Dorfman. The detection of defective members of large populations. Ann. Math. Statist., pages 436-440, 1943. Google Scholar
  9. D. Du and F. K Hwang. Combinatorial group testing and its applications. World Scientific Publishing Company., 2000. Google Scholar
  10. D. Du and F. K Hwang. Pooling design and nonadaptive group testing: important tools for DNA sequencing. World Scientific Publishing Company., 2006. Google Scholar
  11. Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapati, and Ananda Theertha Suresh. Estimating the number of defectives with group testing. In IEEE International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, July 10-15, 2016, pages 1376-1380, 2016. URL: https://doi.org/10.1109/ISIT.2016.7541524.
  12. Edwin S. Hong and Richard E. Ladner. Group testing for image compression. IEEE Trans. Image Processing, 11(8):901-911, 2002. URL: https://doi.org/10.1109/TIP.2002.801124.
  13. F. K. Hwang. A method for detecting all defective members in a population by group testing. Journal of the American Statistical Association, 67:605–-608, 1972. Google Scholar
  14. William H. Kautz and Richard C. Singleton. Nonrandom binary superimposed codes. IEEE Trans. Information Theory, 10(4):363-377, 1964. URL: https://doi.org/10.1109/TIT.1964.1053689.
  15. Joseph L.Gastwirth and Patricia A.Hammick. Estimation of the prevalence of a rare disease, preserving the anonymity of the subjects by group testing: application to estimating the prevalence of aids antibodies in blood donors. Journal of Statistical Planning and Inference., 22(1):15-27, 1989. Google Scholar
  16. C. H. Li. A sequential method for screening experimental variables. J. Amer. Statist. Assoc., 57:455-477, 1962. Google Scholar
  17. Anthony J. Macula and Leonard J. Popyack. A group testing method for finding patterns in data. Discrete Applied Mathematics, 144(1-2):149-157, 2004. URL: https://doi.org/10.1016/j.dam.2003.07.009.
  18. Hung Q. Ngo and Ding-Zhu Du. A survey on combinatorial group testing algorithms with applications to DNA Library Screening. In Discrete Mathematical Problems with Medical Applications, Proceedings of a DIMACS Workshop, December 8-10, 1999, pages 171-182, 1999. URL: https://doi.org/10.1090/dimacs/055/13.
  19. Ely Porat and Amir Rothschild. Explicit Nonadaptive Combinatorial Group Testing Schemes. IEEE Trans. Information Theory, 57(12):7982-7989, 2011. URL: https://doi.org/10.1109/TIT.2011.2163296.
  20. Dana Ron and Gilad Tsur. The Power of an Example: Hidden Set Size Approximation Using Group Queries and Conditional Sampling. CoRR, abs/1404.5568, 2014. URL: http://arxiv.org/abs/1404.5568.
  21. M. Sobel and P. A. Groll. Group testing to eliminate efficiently all defectives in a binomial sample. Bell System Tech. J., 38:1179-1252, 1959. Google Scholar
  22. William H. Swallow. Group Testing for Estimating Infection Rates and Probabilities of Disease Transmission. Phytopathology, 1985. Google Scholar
  23. Keith H. Thompson. Estimation of the Proportion of Vectors in a Natural Population of Insects. Biometrics, 18(4):568-578, 1962. Google Scholar
  24. S. D. Walter, S. W. Hildreth, and B. J. Beaty. Estimation of infection rates in population of organisms using pools of variable size. Am J Epidemiol., 112(1):124-128, 1980. Google Scholar
  25. Jack K. Wolf. Born again group testing: Multiaccess communications. IEEE Trans. Information Theory, 31(2):185-191, 1985. URL: https://doi.org/10.1109/TIT.1985.1057026.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact