Document Open Access Logo

Information-Theoretic and Algorithmic Thresholds for Group Testing

Authors Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Philipp Loick

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.43.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Amin Coja-Oghlan
  • Goethe University, Frankfurt, Germany
Oliver Gebhard
  • Goethe University, Frankfurt, Germany
Max Hahn-Klimroth
  • Goethe University, Frankfurt, Germany
Philipp Loick
  • Goethe University, Frankfurt, Germany

Funding

  • Coja-Oghlan, Amin: Supported of DFG 646/3.
  • Hahn-Klimroth, Max: Supported by Stiftung Polytechnische Gesellschaft.
  • Loick, Philipp: Supported of DFG 646/3.

Acknowledgements

We thank Arya Mazumdar for bringing the group testing problem to our attention.

Cite As Get BibTex

Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, and Philipp Loick. Information-Theoretic and Algorithmic Thresholds for Group Testing. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.43

Abstract

In the group testing problem we aim to identify a small number of infected individuals within a large population. We avail ourselves to a procedure that can test a group of multiple individuals, with the test result coming out positive iff at least one individual in the group is infected. With all tests conducted in parallel, what is the least number of tests required to identify the status of all individuals? In a recent test design [Aldridge et al. 2016] the individuals are assigned to test groups randomly, with every individual joining an equal number of groups. We pinpoint the sharp threshold for the number of tests required in this randomised design so that it is information-theoretically possible to infer the infection status of every individual. Moreover, we analyse two efficient inference algorithms. These results settle conjectures from [Aldridge et al. 2014, Johnson et al. 2019].

Subject Classification

ACM Subject Classification
  • Theory of computation → Theory and algorithms for application domains
  • Theory of computation → Bayesian analysis
  • Theory of computation → Machine learning theory
Keywords
  • Group testing problem
  • phase transitions
  • information theory
  • efficient algorithms
  • sharp threshold
  • Bayesian inference

Metrics

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

Related Versions

References

  1. E. Abbe. Community Detection and Stochastic Block Models: Recent Developments. Journal of Machine Learning Research, 18:1-86, 2018. Google Scholar
  2. D. Achlioptas and A. Coja-Oghlan. Algorithmic barriers from phase transitions. Proc. 49th FOCS, pages 793-802, 2008. Google Scholar
  3. D. Achlioptas, A. Coja-Oghlan, and F. Ricci-Tersenghi. On the solution space geometry of random formulas. Random Structures and Algorithms, 38:251-268, 2011. Google Scholar
  4. D. Achlioptas and C. Moore. Random k-SAT: two moments suffice to cross a sharp threshold. SIAM Journal on Computing, 36:740-762, 2006. Google Scholar
  5. D. Achlioptas, A. Naor, and Y. Peres. Rigorous location of phase transitions in hard optimization problems. Nature, 435:759-764, 2005. Google Scholar
  6. D. Achlioptas and Y. Peres. The threshold for random k-SAT is 2^k log 2 - O(k). Journal of the AMS, 17:947-973, 2004. Google Scholar
  7. M. Aldridge. The capacity of Bernoulli nonadaptive group testing. IEEE Transactions on Information Theory, PP, 2015. Google Scholar
  8. M. Aldridge. On the optimality of some group testing algorithms. Proceedings of IEEE International Symposium on Information Theory, pages 3085-3089, 2017. Google Scholar
  9. M. Aldridge. Individual testing is optimal for nonadaptive group testing in the linear regime. IEEE Transactions on Information Theory, 65:2058-2061, 2018. Google Scholar
  10. M. Aldridge, L. Baldassini, and O. Johnson. Group testing algorithms: bounds and simulations. IEEE Transactions on Information Theory, 60:3671-3687, 2014. Google Scholar
  11. M. Aldridge, O. Johnson, and J. Scarlett. Improved group testing rates with constant column weight designs. Proceedings of IEEE International Symposium on Information Theory, pages 1381-1385, 2016. Google Scholar
  12. A. Alleman. An efficient algorithm for combinatorial group testing. H. Aydinian, F. Cicalese, C. Deppe (eds) Information Theory, Combinatorics, and Search Theory. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, 7777:569-596, 2013. Google Scholar
  13. R. Benz, S. Swamidass, and P. Baldi. Discovery of power-laws in chemical space. Journal of Chemical Information and Modeling, 48:1138-1151, 2008. Google Scholar
  14. H. Chen and F. Hwang. A survey on nonadaptive group testing algorithms through the angle of decoding. Journal of Combinatorial Optimization, 15:49-59, 2008. Google Scholar
  15. A. Coja-Oghlan, F. Krzakala, W. Perkins, and L. Zdeborová. Information-theoretic thresholds from the cavity method. Advances in Mathematics, 333:694-795, 2018. Google Scholar
  16. A. Coja-Oghlan and K. Panagiotou. The asymptotic k-SAT threshold. Advances in Mathematics, 288:985-1068, 2016. Google Scholar
  17. A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Phys. Rev. E, 84:066106, 2011. Google Scholar
  18. J. Ding, A. Sly, and N. Sun. Proof of the satisfiability conjecture for large k. Proc. 47th STOC, pages 59-68, 2015. Google Scholar
  19. R. Dorfman. The detection of defective members of large populations. Annals of Mathematical Statistics, 14:436-440, 1943. Google Scholar
  20. D. Du and F. Hwang. Combinatorial group testing and its applications. World Scientific, 2000. Google Scholar
  21. O. Dubois and J. Mandler. The 3-XORSAT Threshold. Proc. 43rd FOCS, pages 769-778, 2002. Google Scholar
  22. A. Emad and O. Milenkovic. Poisson group testing: a probabilistic model for nonadaptive streaming Boolean compressed sensing. Proc. ICASSP, pages 3335-3339, 2014. Google Scholar
  23. V. Feldman, E. Grigorescu, L. Reyzin, S. Vempala, and Y. Xiao. Statistical algorithms and a lower bound for detecting planted clique. Proc. 45th STOC, pages 655-664, 2013. Google Scholar
  24. V. Feldman, W. Perkins, and S. Vempala. On the complexity of random satisfiability problems with planted solutions. Proc. 48th STOC, pages 77-86, 2015. Google Scholar
  25. D. Gamarnik and M. Sudan. Performance of sequential local algorithms for the random NAE-K-SAT problem. SIAM J. on Computing, 46:590-619, 2017. Google Scholar
  26. S. Hopkins, P. Kothari, A. Potechin, P. Raghavendra, T. Schramm, and D. Steurer. The power of sum-of-squares for detecting hidden structures. Proc. 58th FOCS, pages 720-731, 2017. Google Scholar
  27. S. Janson, T. Luczak, and A. Ruci'nski. Random Graphs. Wiley, 2000. Google Scholar
  28. O. Johnson, M. Aldridge, and J. Scarlett. Performance of group testing algorithms with near-constant tests per item. IEEE Transactions on Information Theory, 65:707-723, 2019. Google Scholar
  29. A. Kolmogorov, A. Nikolaevich, and B. Gnedenko. Limit distributions for sums of independent random variables. Addison-Wesley, 1968. Google Scholar
  30. H. Kwang-Ming and D. Ding-Zhu. Pooling designs and nonadaptive group testing: important tools for DNA sequencing. World Scientific, 2006. Google Scholar
  31. M. Mézard and A. Montanari. Information, physics and computation. Oxford University Press, 2009. Google Scholar
  32. M. Mézard, M. Tarzia, and C. Toninelli. Group testing with random pools: phase transitions and optimal strategy. Journal of Statistical Physics, 131:783-801, 2008. Google Scholar
  33. M. Molloy. The freezing threshold for k-colourings of a random graph. Proc. 43rd STOC, pages 921-930, 2012. Google Scholar
  34. C. Moore. The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness. Bulletin of the EATCS, 121, 2017. Google Scholar
  35. E. Mossel, J. Neeman, and A. Sly. Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields, pages 1-31, 2014. Google Scholar
  36. R. Mourad, Z. Dawy, and F. Morcos. Designing pooling systems for noisy high-throughput protein-protein interaction experiments using Boolean compressed sensing. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 10:1478-1490, 2013. Google Scholar
  37. H. Ngo and D. Du. A survey on combinatorial group testing algorithms with applications to DNA library screening. Discrete Mathematical Problems with Medical Applications, 7:171-182, 2000. Google Scholar
  38. J. Scarlett and V. Cevher. Phase transitions in group testing. Proc. 27th SODA, pages 40-53, 2016. Google Scholar
  39. J. Scarlett and V. Cevher. Limits on support recovery with probabilistic models: an information-theoretic framework. IEEE Transactions on Information Theory, 63:593-620, 2017. Google Scholar
  40. N. Thierry-Mieg. A new pooling strategy for high-throughput screening: the shifted transversal design. BMC Bioinformatics, 7:28, 2006. Google Scholar
  41. L. Zdeborová and F. Krzakala. Statistical physics of inference: thresholds and algorithms. Advances in Physics, 65:453-552, 2016. Google Scholar
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