Improved Non-adaptive algorithms for Threshold Group Testing with a Gap

Improved Non-adaptive algorithms for Threshold Group Testing with a Gap. Bui, T. V., Cheraghchi, M., & Echizen, I. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), 2020.

Link

Paper doi abstract bibtex

The basic goal of threshold group testing is to identify up to $d$ defective items among a population of $n$ items, where $d$ is usually much smaller than $n$. The outcome of a test on a subset of items is positive if the subset has at least $u$ defective items, negative if it has up to $\ell$ defective items, where $0 ≤ \ell < u$, and arbitrary otherwise. This is called threshold group testing. The parameter $g = u - \ell - 1$ is called the gap. In this paper, we focus on the case $g > 0$, i.e., threshold group testing with a gap. Note that the results presented here are also applicable to the case $g = 0$; however, the results are not as efficient as those in related work. Currently, a few reported studies have investigated test designs and decoding algorithms for identifying defective items. Most of the previous studies have not been feasible because there are numerous constraints on their problem settings or the decoding complexities of their proposed schemes are relatively large. Therefore, it is compulsory to reduce the number of tests as well as the decoding complexity, i.e., the time for identifying the defective items, for achieving practical schemes. The work presented here makes five contributions. The first is a more accurate theorem for a non-adaptive algorithm for threshold group testing proposed by Chen and Fu. The second is an improvement in the construction of disjunct matrices, which are the main tools for tackling (threshold) group testing and other tasks such as constructing cover-free families or learning hidden graphs. Specifically, we present a better upper bound on the number of tests for disjunct matrices compared with that in related work. The third and fourth contributions are a reduction in the number of tests and a reduction in the decoding time for identifying defective items in a noisy setting on test outcomes. The fifth contribution is a simulation on the number of tests of the resulting improvements for previous work and the proposed theorems.

@INPROCEEDINGS{ref:BCE20,
  author =	 {Thach V. Bui and Mahdi Cheraghchi and Isao Echizen},
  title =	 {Improved Non-adaptive algorithms for Threshold Group
                  Testing with a Gap},
  year =	 2020,
  booktitle =	 {Proceedings of the {IEEE International Symposium on
                  Information Theory (ISIT)}},
  doi =		 {10.1109/ISIT44484.2020.9174212},
  url_Link = {https://ieeexplore.ieee.org/document/9174212},
  url_Paper =	 {https://arxiv.org/abs/2001.01008},
  abstract =	 {The basic goal of threshold group testing is to
                  identify up to $d$ defective items among a
                  population of $n$ items, where $d$ is usually much
                  smaller than $n$. The outcome of a test on a subset
                  of items is positive if the subset has at least $u$
                  defective items, negative if it has up to $\ell$
                  defective items, where $0 \leq \ell < u$, and
                  arbitrary otherwise. This is called threshold group
                  testing. The parameter $g = u - \ell - 1$ is called
                  \textit{the gap}. In this paper, we focus on the
                  case $g > 0$, i.e., threshold group testing with a
                  gap. Note that the results presented here are also
                  applicable to the case $g = 0$; however, the results
                  are not as efficient as those in related
                  work. Currently, a few reported studies have
                  investigated test designs and decoding algorithms
                  for identifying defective items. Most of the
                  previous studies have not been feasible because
                  there are numerous constraints on their problem
                  settings or the decoding complexities of their
                  proposed schemes are relatively large. Therefore, it
                  is compulsory to reduce the number of tests as well
                  as the decoding complexity, i.e., the time for
                  identifying the defective items, for achieving
                  practical schemes.  The work presented here makes
                  five contributions. The first is a more accurate
                  theorem for a non-adaptive algorithm for threshold
                  group testing proposed by Chen and Fu. The second is
                  an improvement in the construction of disjunct
                  matrices, which are the main tools for tackling
                  (threshold) group testing and other tasks such as
                  constructing cover-free families or learning hidden
                  graphs. Specifically, we present a better upper
                  bound on the number of tests for disjunct matrices
                  compared with that in related work. The third and
                  fourth contributions are a reduction in the number
                  of tests and a reduction in the decoding time for
                  identifying defective items in a noisy setting on
                  test outcomes. The fifth contribution is a
                  simulation on the number of tests of the resulting
                  improvements for previous work and the proposed
                  theorems.  }
}

Downloads: 0