Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.16370 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917675881463808 |
|---|---|
| author | Wang, Hsin-Po Gabrys, Ryan Guruswami, Venkatesan |
| author_facet | Wang, Hsin-Po Gabrys, Ryan Guruswami, Venkatesan |
| contents | We modify Cheraghchi-Nakos [CN20] and Price-Scarlett's [PS20] fast binary splitting approach to nonadaptive group testing. We show that, to identify a uniformly random subset of $k$ infected persons among a population of $n$, it takes only $\ln(2 - 4\varepsilon) ^{-2} k \ln n$ tests and decoding complexity $O(\varepsilon^{-2} k \ln n)$, for any small $\varepsilon > 0$, with vanishing error probability. In works prior to ours, only two types of group testing schemes exist. Those that use $\ln(2)^{-2} k \ln n$ or fewer tests require linear-in-$n$ complexity, sometimes even polynomial in $n$; those that enjoy sub-$n$ complexity employ $O(k \ln n)$ tests, where the big-$O$ scalar is implicit, presumably greater than $\ln(2)^{-2}$. We almost achieve the best of both worlds, namely, the almost-$\ln(2)^{-2}$ scalar and the sub-$n$ decoding complexity. How much further one can reduce the scalar $\ln(2)^{-2}$ remains an open problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_16370 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quickly-Decodable Group Testing with Fewer Tests: Price-Scarlett and Cheraghchi-Nakos's Nonadaptive Splitting with Explicit Scalars Wang, Hsin-Po Gabrys, Ryan Guruswami, Venkatesan Information Theory We modify Cheraghchi-Nakos [CN20] and Price-Scarlett's [PS20] fast binary splitting approach to nonadaptive group testing. We show that, to identify a uniformly random subset of $k$ infected persons among a population of $n$, it takes only $\ln(2 - 4\varepsilon) ^{-2} k \ln n$ tests and decoding complexity $O(\varepsilon^{-2} k \ln n)$, for any small $\varepsilon > 0$, with vanishing error probability. In works prior to ours, only two types of group testing schemes exist. Those that use $\ln(2)^{-2} k \ln n$ or fewer tests require linear-in-$n$ complexity, sometimes even polynomial in $n$; those that enjoy sub-$n$ complexity employ $O(k \ln n)$ tests, where the big-$O$ scalar is implicit, presumably greater than $\ln(2)^{-2}$. We almost achieve the best of both worlds, namely, the almost-$\ln(2)^{-2}$ scalar and the sub-$n$ decoding complexity. How much further one can reduce the scalar $\ln(2)^{-2}$ remains an open problem. |
| title | Quickly-Decodable Group Testing with Fewer Tests: Price-Scarlett and Cheraghchi-Nakos's Nonadaptive Splitting with Explicit Scalars |
| topic | Information Theory |
| url | https://arxiv.org/abs/2405.16370 |