Efficiently Decodable Non-Adaptive Threshold Group Testing

Efficiently Decodable Non-Adaptive Threshold Group Testing. Bui, T. V., Kuribayashi, M., Cheraghchi, M., & Echizen, I. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), pages 2584–2588, 2018. Extended version in IEEE Transactions on Information Theory.

Link

Paper doi abstract bibtex

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 $2 ≤ u ≤ 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} (u łog{\frac{d}{u}} + łog{\frac{1}{ε}} ) · d^2 łog{n} )$ tests with probability at least $1 - ε$ for any $ε > 0$ or $t = O ( ( \frac{d}{u} )^u ( \frac{d}{d -u} )^{d - u} d^3 łog{n} · łog{\frac{n}{d}} )$ tests with probability 1. The decoding time is $t × \mathrm{poly}(d^2 łog{n})$. This result significantly improves the best known results for decoding non-adaptive threshold group testing: $O(nłog{n} + n łog{\frac{1}{ε}})$ for probabilistic decoding, where $ε > 0$, and $O(n^u łog{n})$ for deterministic decoding.

@INPROCEEDINGS{ref:conf:BKCE18,
  author =	 {Thach V. Bui and Minoru Kuribayashi and Mahdi
                  Cheraghchi and Isao Echizen},
  title =	 {Efficiently Decodable Non-Adaptive Threshold Group
                  Testing},
  year =	 2018,
  booktitle =	 {Proceedings of the {IEEE International Symposium on
                  Information Theory (ISIT)}},
  note =	 {Extended version in {IEEE Transactions on
                  Information Theory}.},
  pages =	 {2584--2588},
  doi =		 {10.1109/ISIT.2018.8437847},
  url_Link =	 {https://ieeexplore.ieee.org/document/8437847},
  url_Paper =	 {https://arxiv.org/abs/1712.07509},
  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 $2 \leq u \leq 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} (u \log{\frac{d}{u}} +
                  \log{\frac{1}{\epsilon}} ) \cdot d^2 \log{n} )$
                  tests with probability at least $1 - \epsilon$ for
                  any $\epsilon > 0$ or $t = O ( ( \frac{d}{u} )^u (
                  \frac{d}{d -u} )^{d - u} d^3 \log{n} \cdot
                  \log{\frac{n}{d}} )$ tests with probability 1. The
                  decoding time is $t \times \mathrm{poly}(d^2
                  \log{n})$. This result significantly improves the
                  best known results for decoding non-adaptive
                  threshold group testing: $O(n\log{n} + n
                  \log{\frac{1}{\epsilon}})$ for probabilistic
                  decoding, where $\epsilon > 0$, and $O(n^u \log{n})$
                  for deterministic decoding.  }
}

Downloads: 0