Name
Abstract | ||
|---|---|---|
We consider non-adaptive threshold group testing for identification of up to $d$ defective items in a set of $n$ items, where a test is positive if it contains at least $2leq uleq d$ defective items, and negative otherwise. The defective items can be identified using $t=O(( frac{d}{u})^{u}(frac{d}{d-u})^{d-u}(ulogfrac{d}{u}+logfrac{1}{epsilon})d^{2}log n)$ tests with probability at least $1-epsilon$ for any $epsilon u003e 0$ or $t= Oleft(left(frac{b}{u}right)^{u}left(frac{d}{d-u}right)^{d-u}cdot d^{3}log n cdot log frac{n}{d}right)$ tests with probability 1. The decoding time is $ttimes$ poly $(d^{2}log n)$ . This result significantly improves the best known results for decoding non-adaptive threshold group testing: $O(n log n+nlogfrac{1}{epsilon})$ for probabilistic decoding, where $epsilon u003e 0$ , and $O(n^{u}log n)$ for deterministic decoding. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/TIT.2019.2907990 | international symposium on information theory |
Keywords | DocType | Volume |
Decoding,Testing,Complexity theory,Matrix converters,Probabilistic logic,Indexes,Sociology | Conference | abs/1712.07509 |
Issue | ISSN | Citations |
9 | 0018-9448 | 4 |
PageRank | References | Authors |
0.44 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thach V. Bui | 1 | 21 | 7.65 |
| Minoru Kuribayashi | 2 | 23 | 19.55 |
| Mahdi Cheraghchi | 3 | 221 | 21.86 |
| Isao Echizen | 4 | 299 | 68.82 |