Efficiently Decodable Non-Adaptive Threshold Group Testing

DOI10.1109/TIT.2019.2907990MaRDI QIDQ5211383zbMATH OpenOpenAlexFDO

Authors Thach V. Bui, Minoru Kuribayashi, Mahdi Cheraghchi, Isao Echizen

Publication date 28 January 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.07509

Mathematics Subject Classification ID

Fault detection; testing in circuits and networks (94C12)

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 $2lequleqd$ defective items, and negative otherwise. The defective items can be identified using $t=Oleft(left(fracduight{)}^{u}left(fracdd-uight{)}^{d-u}left(ulogfracdu+logfrac1epsilonight)cdot{d}^{2}lognight)$ tests with probability at least $1-epsilon$ for any $epsilon>0$ or $t=Oleft(left(fracduight{)}^{u}left(fracdd-uight{)}^{d-u}{d}^{3}logncdotlogfracndight)$ tests with probability 1. The decoding time is $timesmathrmpoly(d^{2}logn)$. This result significantly improves the best known results for decoding non-adaptive threshold group testing: $O(nlogn+nlogfrac1epsilon)$ for probabilistic decoding, where $epsilon>0$, and $O(n^{u}logn)$ for deterministic decoding.

Cited in

(4)

• Nonadaptive algorithms for threshold group testing
• Group testing: revisiting the ideas
• Non-adaptive Group-Testing Aggregate MAC Scheme
• Erasure combinatorial batch codes based on nonadaptive group testing

This page was built for publication: Efficiently Decodable Non-Adaptive Threshold Group Testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5211383)