{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T06:26:32Z","timestamp":1774419992337,"version":"3.50.1"},"reference-count":41,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2021,1,28]],"date-time":"2021-01-28T00:00:00Z","timestamp":1611792000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In the group testing problem the aim is to identify a small set of <jats:italic>k<\/jats:italic> \u2053 <jats:italic>n<\/jats:italic><jats:sup><jats:italic>\u03b8<\/jats:italic><\/jats:sup> infected individuals out of a population size <jats:italic>n<\/jats:italic>, 0 &lt; <jats:italic>\u03b8<\/jats:italic> &lt; 1. We avail ourselves of a test procedure capable of testing groups of individuals, with the test returning a positive result if and only if at least one individual in the group is infected. The aim is to devise a test design with as few tests as possible so that the set of infected individuals can be identified correctly with high probability. We establish an explicit sharp information-theoretic\/algorithmic phase transition <jats:italic>m<\/jats:italic><jats:sub>inf<\/jats:sub> for non-adaptive group testing, where all tests are conducted in parallel. Thus with more than <jats:italic>m<\/jats:italic><jats:sub>inf<\/jats:sub> tests the infected individuals can be identified in polynomial time with high probability, while learning the set of infected individuals is information-theoretically impossible with fewer tests. In addition, we develop an optimal adaptive scheme where the tests are conducted in two stages.<\/jats:p>","DOI":"10.1017\/s096354832100002x","type":"journal-article","created":{"date-parts":[[2021,1,28]],"date-time":"2021-01-28T05:54:52Z","timestamp":1611813292000},"page":"811-848","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":17,"title":["Optimal group testing"],"prefix":"10.1017","volume":"30","author":[{"given":"Amin","family":"Coja-Oghlan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oliver","family":"Gebhard","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Max","family":"Hahn-Klimroth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philipp","family":"Loick","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2021,1,28]]},"reference":[{"key":"S096354832100002X_ref18","first-page":"229","article-title":"On two problems of information theory","volume":"8","author":"Erd\u00f6s","year":"1963","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl"},{"key":"S096354832100002X_ref29","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2280915"},{"key":"S096354832100002X_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<457::AID-RSA14>3.0.CO;2-W"},{"key":"S096354832100002X_ref16","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177731363"},{"key":"S096354832100002X_ref33","unstructured":"[33] Reeves, G. and Pfister, H. (2019) Understanding phase transitions via mutual information and MMSE. arXiv:1907.02095"},{"key":"S096354832100002X_ref12","unstructured":"[12] Coja-Oghlan, A. , Gebhard, O. , Hahn-Klimroth, M. and Loick, P. (2019) Information-theoretic and algorithmic thresholds for group testing. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), #43. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik."},{"key":"S096354832100002X_ref20","volume-title":"The Ellipsoid Method and Combinatorial Optimization.","author":"Gr\u00f6tschel","year":"1988"},{"key":"S096354832100002X_ref4","doi-asserted-by":"crossref","first-page":"2058","DOI":"10.1109\/TIT.2018.2873136","article-title":"Individual testing is optimal for nonadaptive group testing in the linear regime","volume":"65","author":"Aldridge","year":"2019","journal-title":"IEEE Trans. Inform. Theory"},{"key":"S096354832100002X_ref26","article-title":"Statistical-physics-based reconstruction in compressed sensing","volume":"2","author":"Krzakala","year":"2012","journal-title":"Phys. Rev. X"},{"key":"S096354832100002X_ref17","first-page":"166","article-title":"Bounds on the length of disjunctive codes","volume":"18","author":"D\u2019yachkov","year":"1982","journal-title":"Problemy Peredachi Informatsii"},{"key":"S096354832100002X_ref13","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.84.066106"},{"key":"S096354832100002X_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-007-9083-3"},{"key":"S096354832100002X_ref8","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2021379"},{"key":"S096354832100002X_ref28","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2095072"},{"key":"S096354832100002X_ref9","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2002.1013122"},{"key":"S096354832100002X_ref1","first-page":"6446","article-title":"Community detection and stochastic block models: recent developments","volume":"18","author":"Abbe","year":"2017","journal-title":"J. Mach. Learning Res."},{"key":"S096354832100002X_ref10","unstructured":"[10] Brennan, M. and Bresler, G. (2019) Optimal average-case reductions to sparse PCA: from weak assumptions to strong hardness. Proc. Mach. Learning Res. 99 469\u2013470"},{"key":"S096354832100002X_ref25","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1964.1053689"},{"key":"S096354832100002X_ref31","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-008-9528-9"},{"key":"S096354832100002X_ref27","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2010.5706927"},{"key":"S096354832100002X_ref14","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"S096354832100002X_ref24","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1109\/TIT.2018.2861772","article-title":"Performance of group testing algorithms with near-constant tests per item","volume":"65","author":"Johnson","year":"2018","journal-title":"IEEE Trans. Inform. Theory"},{"key":"S096354832100002X_ref39","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0021197"},{"key":"S096354832100002X_ref32","article-title":"The computer science and physics of community detection: landscapes, phase transitions, and hardness","volume":"121","author":"Moore","year":"2017","journal-title":"Bull. EATCS"},{"key":"S096354832100002X_ref3","doi-asserted-by":"publisher","DOI":"10.1137\/18M1183339"},{"key":"S096354832100002X_ref5","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2314472"},{"key":"S096354832100002X_ref30","volume-title":"Pooling Designs and Nonadaptive Group Testing: Important Tools for DNA Sequencing.","author":"Kwang-Ming","year":"2006"},{"key":"S096354832100002X_ref36","doi-asserted-by":"publisher","DOI":"10.1109\/COMPTELIX.2017.8004055"},{"key":"S096354832100002X_ref23","unstructured":"[23] Janson, S. , \u0141uczak, T. and Ruci\u0144ski, A. (2011) Random Graphs. Wiley."},{"key":"S096354832100002X_ref37","doi-asserted-by":"crossref","unstructured":"[37] Takeuchi, K. , Tanaka, T. and Kawabata, T. (2011) Improvement of BP-based CDMA multiuser detection by spatial coupling. In 2011 IEEE International Symposium on Information Theory, pp. 1489\u20131493. IEEE.","DOI":"10.1109\/ISIT.2011.6033789"},{"key":"S096354832100002X_ref6","doi-asserted-by":"publisher","DOI":"10.1561\/0100000099"},{"key":"S096354832100002X_ref19","doi-asserted-by":"publisher","DOI":"10.1109\/18.782171"},{"key":"S096354832100002X_ref40","doi-asserted-by":"crossref","unstructured":"[40] Wu, Y. and Verd\u00fa, S. (2010) R\u00e9nyi information dimension: fundamental limits of almost lossless analog compression. IEEE Trans. Inform. Theory 56 3721\u20133748.","DOI":"10.1109\/TIT.2010.2050803"},{"key":"S096354832100002X_ref15","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2274513"},{"key":"S096354832100002X_ref2","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1109\/TIT.2018.2855698","article-title":"Decoding from pooled data: phase transitions of message passing","volume":"65","author":"Alaoui","year":"2019","journal-title":"IEEE Trans. Inform. Theory"},{"key":"S096354832100002X_ref21","author":"Hoeffding","year":"1994"},{"key":"S096354832100002X_ref35","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2019.8849310"},{"key":"S096354832100002X_ref34","doi-asserted-by":"crossref","unstructured":"[34] Scarlett, J. (2018) Noisy adaptive group testing: bounds and algorithms. IEEE Trans. Inform. Theory 65 3646\u20133661.","DOI":"10.1109\/TIT.2018.2883604"},{"key":"S096354832100002X_ref41","doi-asserted-by":"crossref","unstructured":"[41] Zdeborov\u00e1, L. and Krzakala, F. (2016) Statistical physics of inference: thresholds and algorithms. Adv. Phys. 65 453\u2013552.","DOI":"10.1080\/00018732.2016.1211393"},{"key":"S096354832100002X_ref22","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1972.10481257"},{"key":"S096354832100002X_ref38","doi-asserted-by":"crossref","unstructured":"[38] Ungar, P. (1960) The cutoff point for group testing. Commun. Pure Appl. Math. 13 49\u201354.","DOI":"10.1002\/cpa.3160130105"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096354832100002X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T15:52:04Z","timestamp":1634313124000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096354832100002X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,28]]},"references-count":41,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["S096354832100002X"],"URL":"https:\/\/doi.org\/10.1017\/s096354832100002x","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,28]]},"assertion":[{"value":"\u00a9 The Author(s), 2021. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}