TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. TUHH
  3. Publications
  4. Noisy group testing via spatial coupling
 
Options

Noisy group testing via spatial coupling

Citation Link: https://doi.org/10.15480/882.13884
Publikationstyp
Journal Article
Date Issued
2024-11-19
Sprache
English
Author(s)
Coja-Oghlan, Amin  
Hahn-Klimroth, Maximilian Grischa  
Hintze, Lukas  
Kaaser, Dominik 
Data Engineering E-19  
Krieg, Lena  
Rolvien, Maurice
Scheftelowitsch, Olga
TORE-DOI
10.15480/882.13884
TORE-URI
https://hdl.handle.net/11420/52406
Journal
Combinatorics, probability & computing  
Citation
Combinatorics Probability and Computing (in Press): (2024)
Publisher DOI
10.1017/S0963548324000336
Scopus ID
2-s2.0-85196577395
We 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.
Subjects
efficient algorithms | Group testing | inference | random graphs
DDC Class
519: Applied Mathematics, Probabilities
004: Computer Sciences
610: Medicine, Health
Lizenz
https://creativecommons.org/licenses/by/4.0/
Loading...
Thumbnail Image
Name

noisy-group-testing-via-spatial-coupling.pdf

Type

Main Article

Size

956.38 KB

Format

Adobe PDF

TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback