Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.16374 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917675902435328 |
|---|---|
| author | Wang, Hsin-Po Guruswami, Venkatesan |
| author_facet | Wang, Hsin-Po Guruswami, Venkatesan |
| contents | Group testing (GT) is the art of identifying binary signals and the marketplace for exchanging new ideas for related fields such as unique-element counting, compressed sensing, traitor tracing, and geno-typing. A GT scheme can be nonadaptive or adaptive; the latter is preferred when latency is ess of an issue. To construct adaptive GT schemes, a popular strategy is to spend the majority of tests in the first few rounds to gain as much information as possible, and uses later rounds to refine details. In this paper, we propose a transparent strategy called "isolate and then identify" (I@I). In the first few rounds, I@I divides the population into teams until every team contains at most one sick person. Then, in the last round, I@I identifies the sick person in each team. Performance-wise, I@I is the first GT scheme that achieves the optimal coefficient $1/$capacity$(Z)$ for the $k \log_2 (n/k)$ term in the number of tests when $Z$ is a generic channel corrupting the test outcomes. I@I follows a modular methodology whereby the isolating part and the identification part can be optimized separately. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_16374 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Isolate and then Identify: Rethinking Adaptive Group Testing Wang, Hsin-Po Guruswami, Venkatesan Information Theory Group testing (GT) is the art of identifying binary signals and the marketplace for exchanging new ideas for related fields such as unique-element counting, compressed sensing, traitor tracing, and geno-typing. A GT scheme can be nonadaptive or adaptive; the latter is preferred when latency is ess of an issue. To construct adaptive GT schemes, a popular strategy is to spend the majority of tests in the first few rounds to gain as much information as possible, and uses later rounds to refine details. In this paper, we propose a transparent strategy called "isolate and then identify" (I@I). In the first few rounds, I@I divides the population into teams until every team contains at most one sick person. Then, in the last round, I@I identifies the sick person in each team. Performance-wise, I@I is the first GT scheme that achieves the optimal coefficient $1/$capacity$(Z)$ for the $k \log_2 (n/k)$ term in the number of tests when $Z$ is a generic channel corrupting the test outcomes. I@I follows a modular methodology whereby the isolating part and the identification part can be optimized separately. |
| title | Isolate and then Identify: Rethinking Adaptive Group Testing |
| topic | Information Theory |
| url | https://arxiv.org/abs/2405.16374 |