Small-Error Cascaded Group Testing
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909034569793536 |
|---|---|
| author | McMorrow, Daniel Karamchandani, Nikhil Jaggi, Sidharth |
| author_facet | McMorrow, Daniel Karamchandani, Nikhil Jaggi, Sidharth |
| contents | Group testing concerns itself with the accurate recovery of a set of "defective" items from a larger population via a series of tests. While most works in this area have considered the classical group testing model, where tests are binary and indicate the presence of at least one defective item in the test, we study the cascaded group testing model. In cascaded group testing, tests admit an ordering, and test outcomes indicate the first defective item in the test under this ordering. Under this model, we establish various achievability bounds for several different recovery criteria using both non-adaptive and adaptive test designs when assuming both unconstrained and constrained test sizes. In the constrained test size setting, we also provide a lower bound showing our achievability result is optimal up to logarithmic factors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_11945 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Small-Error Cascaded Group Testing McMorrow, Daniel Karamchandani, Nikhil Jaggi, Sidharth Information Theory Group testing concerns itself with the accurate recovery of a set of "defective" items from a larger population via a series of tests. While most works in this area have considered the classical group testing model, where tests are binary and indicate the presence of at least one defective item in the test, we study the cascaded group testing model. In cascaded group testing, tests admit an ordering, and test outcomes indicate the first defective item in the test under this ordering. Under this model, we establish various achievability bounds for several different recovery criteria using both non-adaptive and adaptive test designs when assuming both unconstrained and constrained test sizes. In the constrained test size setting, we also provide a lower bound showing our achievability result is optimal up to logarithmic factors. |
| title | Small-Error Cascaded Group Testing |
| topic | Information Theory |
| url | https://arxiv.org/abs/2601.11945 |