Noisy group testing via spatial coupling
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915181912653824 |
|---|---|
| author | Coja-Oghlan, Amin Hahn-Klimroth, Max Hintze, Lukas Kaaser, Dominik Krieg, Lena Rolvien, Maurice Scheftelowitsch, Olga |
| author_facet | Coja-Oghlan, Amin Hahn-Klimroth, Max Hintze, Lukas Kaaser, Dominik Krieg, Lena Rolvien, Maurice Scheftelowitsch, Olga |
| contents | We study the problem of identifying a small set $k\sim 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, i.e.\ 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 results 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 matches the information-theoretic lower bound for the constant column design, a powerful and well-studied test design. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_02895 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Noisy group testing via spatial coupling Coja-Oghlan, Amin Hahn-Klimroth, Max Hintze, Lukas Kaaser, Dominik Krieg, Lena Rolvien, Maurice Scheftelowitsch, Olga Discrete Mathematics Information Theory Combinatorics 05C80, 62B10, 68P30, 68R05 F.2.2 We study the problem of identifying a small set $k\sim 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, i.e.\ 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 results 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 matches the information-theoretic lower bound for the constant column design, a powerful and well-studied test design. |
| title | Noisy group testing via spatial coupling |
| topic | Discrete Mathematics Information Theory Combinatorics 05C80, 62B10, 68P30, 68R05 F.2.2 |
| url | https://arxiv.org/abs/2402.02895 |