Noisy group testing via spatial coupling

Simple item page
dc.contributor.authorCoja-Oghlan, Amin
dc.contributor.authorHahn-Klimroth, Max
dc.contributor.authorHintze, Lukas
dc.contributor.authorKaaser, Dominik
dc.contributor.authorKrieg, Lena
dc.contributor.authorRolvien, Maurice
dc.contributor.authorScheftelowitsch, Olga
dc.date.accessioned2025-09-15T12:33:26Z
dc.date.available2025-09-15T12:33:26Z
dc.date.issued2024-11-19
dc.description.abstractWe study the problem of identifying a small number k∼nθ, 0<θ<1, of infected individuals within a large population of size n 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 o(k) 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.en
dc.identifier.urihttp://hdl.handle.net/2003/43972
dc.language.isoen
dc.relation.ispartofseriesCombinatorics, probability & computing; 34(2)
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.subjectGroup testingen
dc.subjectRandom graphsen
dc.subjectInferenceen
dc.subjectEfficient algorithmsen
dc.subject.ddc004
dc.titleNoisy group testing via spatial couplingen
dc.typeText
dc.type.publicationtypeArticle
dcterms.accessRightsopen access
eldorado.dnb.deposittrue
eldorado.doi.registerfalse
eldorado.secondarypublicationtrue
eldorado.secondarypublication.primarycitationCoja-Oghlan A, Hahn-Klimroth M, Hintze L, et al. Noisy group testing via spatial coupling. Combinatorics, Probability and Computing. 2025;34(2):210-258. doi:10.1017/S0963548324000336
eldorado.secondarypublication.primaryidentifierhttps://doi.org/10.1017/S0963548324000336

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
noisy-group-testing-via-spatial-coupling.pdf
Size:
960.87 KB
Format:
Adobe Portable Document Format
Description:
DNB
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
4.82 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

LS 02 Komplexitätstheorie und Effiziente Algorithmen