{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T04:36:40Z","timestamp":1778647000905,"version":"3.51.4"},"reference-count":43,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2024,11,19]],"date-time":"2024-11-19T00:00:00Z","timestamp":1731974400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the problem of identifying a small number <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000336_inline1.png\"\/><jats:tex-math>\n$k\\sim n^\\theta$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000336_inline2.png\"\/><jats:tex-math>\n$0\\lt \\theta \\lt 1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, of infected individuals within a large population of size <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000336_inline3.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> by testing groups of individuals simultaneously. All tests are conducted concurrently. The goal is to minimise the total number of tests required. In this paper, we make the (realistic) assumption that tests are noisy, that is, that a group that contains an infected individual may return a negative test result or one that does not contain an infected individual may return a positive test result with a certain probability. The noise need not be symmetric. We develop an algorithm called SPARC that correctly identifies the set of infected individuals up to <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000336_inline4.png\"\/><jats:tex-math>\n$o(k)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> errors with high probability with the asymptotically minimum number of tests. Additionally, we develop an algorithm called SPEX that exactly identifies the set of infected individuals w.h.p. with a number of tests that match the information-theoretic lower bound for the constant column design, a powerful and well-studied test design.<\/jats:p>","DOI":"10.1017\/s0963548324000336","type":"journal-article","created":{"date-parts":[[2024,11,19]],"date-time":"2024-11-19T08:48:55Z","timestamp":1732006135000},"page":"210-258","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":3,"title":["Noisy group testing via spatial coupling"],"prefix":"10.1017","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7350-1418","authenticated-orcid":false,"given":"Amin","family":"Coja-Oghlan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Max","family":"Hahn-Klimroth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lukas","family":"Hintze","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dominik","family":"Kaaser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5302-6955","authenticated-orcid":false,"given":"Lena","family":"Krieg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maurice","family":"Rolvien","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Olga","family":"Scheftelowitsch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2024,11,19]]},"reference":[{"key":"S0963548324000336_ref24","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2861772"},{"key":"S0963548324000336_ref8","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.3023377"},{"key":"S0963548324000336_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S096354832100002X"},{"key":"S0963548324000336_ref5","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2013.6620712"},{"key":"S0963548324000336_ref32","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2883604"},{"key":"S0963548324000336_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0019-y"},{"key":"S0963548324000336_ref1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2748564"},{"key":"S0963548324000336_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2018.05.029"},{"key":"S0963548324000336_ref40","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2022.3212730"},{"key":"S0963548324000336_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M"},{"key":"S0963548324000336_ref4","doi-asserted-by":"publisher","DOI":"10.1561\/0100000099"},{"key":"S0963548324000336_ref26","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2010.5706927"},{"key":"S0963548324000336_ref20","unstructured":"[20] Hahn-Klimroth, M. and M\u00fcller, N. (2022) Near optimal efficient decoding from pooled data, pp. 3395\u20133409. In Proc. 35th COLT."},{"key":"S0963548324000336_ref14","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2274513"},{"key":"S0963548324000336_ref10","unstructured":"[10] Coja-Oghlan, A. , Gebhard, O. , Hahn-Klimroth, M. , Wein, A. and Zadik, I. (2022) Statistical and computational phase transitions in group testing, pp. 4764\u20134781. In Proc. 35th COLT."},{"key":"S0963548324000336_ref19","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2021.3138489"},{"key":"S0963548324000336_ref15","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177731363"},{"key":"S0963548324000336_ref23","volume-title":"Random Graphs","author":"Janson","year":"2011"},{"key":"S0963548324000336_ref34","doi-asserted-by":"publisher","DOI":"10.1017\/9781108616799.017"},{"key":"S0963548324000336_ref41","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0021197"},{"key":"S0963548324000336_ref3","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2873136"},{"key":"S0963548324000336_ref17","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2855698"},{"key":"S0963548324000336_ref28","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2360692"},{"key":"S0963548324000336_ref22","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1972.10481257"},{"key":"S0963548324000336_ref30","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001"},{"key":"S0963548324000336_ref36","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2010.5707018"},{"key":"S0963548324000336_ref37","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2011.6033789"},{"key":"S0963548324000336_ref33","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch4"},{"key":"S0963548324000336_ref29","volume-title":"Principles and practice of pediatric infectious diseases","author":"Long","year":"2018"},{"key":"S0963548324000336_ref31","volume-title":"Probabilistic reasoning in intelligent systems: networks of plausible inference","author":"Pearl","year":"1988"},{"key":"S0963548324000336_ref7","volume-title":"Exact Thresholds for Noisy Non-Adaptive Group Testing","author":"Chen","year":"2024"},{"key":"S0963548324000336_ref38","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2022.3140604"},{"key":"S0963548324000336_ref39","doi-asserted-by":"publisher","DOI":"10.1109\/JSAIT.2020.3039790"},{"key":"S0963548324000336_ref11","unstructured":"[11] Coja-Oghlan, A. , Hahn-Klimroth, M. , Loick, P. and Penschuck, M. (2021) Penschuck: Efficient and accurate group testing via Belief Propagation: an empirical study, pp. 18. Proc. 20th SEA, 8(1-8)"},{"key":"S0963548324000336_ref27","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2280915"},{"key":"S0963548324000336_ref6","doi-asserted-by":"publisher","DOI":"10.1109\/Allerton.2011.6120391"},{"key":"S0963548324000336_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0865-5_26"},{"key":"S0963548324000336_ref25","first-page":"021005","article-title":"Statistical-physics-based reconstruction in compressed sensing","volume":"2","author":"Krzakala","year":"2012","journal-title":"Phys. Rev. X"},{"key":"S0963548324000336_ref42","doi-asserted-by":"publisher","DOI":"10.1080\/00018732.2016.1211393"},{"key":"S0963548324000336_ref18","doi-asserted-by":"publisher","DOI":"10.1137\/18M1183339"},{"key":"S0963548324000336_ref35","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.2970184"},{"key":"S0963548324000336_ref43","first-page":"1409","article-title":"Non-adaptive pooling strategies for detection of rare faulty items","author":"Zhang","year":"2013","journal-title":"IEEE Int. Conf. Comm. Workshops (ICC)"},{"key":"S0963548324000336_ref2","first-page":"236","article-title":"Rates of adaptive group testing in the linear regime","author":"Aldridge","year":"2019","journal-title":"IEEE Int. Symp. Info. Theory"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548324000336","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,24]],"date-time":"2025-02-24T12:38:45Z","timestamp":1740400725000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548324000336\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,19]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["S0963548324000336"],"URL":"https:\/\/doi.org\/10.1017\/s0963548324000336","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,19]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}