Combinatorial Group Testing Schemes with Near-Optimal Decoding Time

Combinatorial Group Testing Schemes with Near-Optimal Decoding Time. Cheraghchi, M. & Nakos, V. In Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020.

Link

Paper doi abstract bibtex

In the long-studied problem of combinatorial group testing, one is asked to detect a set of $k$ defective items out of a population of size $n$, using $m ≪ n$ disjunctive measurements. In the non-adaptive setting, the most widely used combinatorial objects are disjunct and list-disjunct matrices, which define incidence matrices of test schemes. Disjunct matrices allow the identification of the exact set of defectives, whereas list disjunct matrices identify a small superset of the defectives. Apart from the combinatorial guarantees, it is often of key interest to equip measurement designs with efficient decoding algorithms. The most efficient decoders should run in sublinear time in $n$, and ideally near-linear in the number of measurements $m$. In this work, we give several constructions with an optimal number of measurements and near-optimal decoding time for the most fundamental group testing tasks, as well as for central tasks in the compressed sensing and heavy hitters literature. For many of those tasks, the previous measurement-optimal constructions needed time either quadratic in the number of measurements or linear in the universe size. Among our results are the following: a construction of disjunct matrices matching the best known construction in terms of the number of rows $m$, but achieving $O(m)$ decoding time. a construction of list disjunct matrices with the optimal $m=O(k łog(n/k))$ number of rows and nearly linear decoding time in $m$; error-tolerant variations of the above constructions; a non-adaptive group testing scheme for the "for-each" model with $m=O(k łog n)$ measurements and $O(m)$ decoding time; a streaming algorithm for the "for-all" version of the heavy hitters problem in the strict turnstile model with near-optimal query time, as well as a "list decoding" variant obtaining also near-optimal update time and $O(kłog(n/k))$ space usage; an $\ell_2/\ell_2$ weak identification system for compressed sensing with nearly optimal sample complexity and nearly linear decoding time in the sketch length. Most of our results are obtained via a clean and novel approach which avoids list-recoverable codes or related complex techniques which were present in almost every state-of-the-art work on efficiently decodable constructions of such objects.

@INPROCEEDINGS{ref:CN20,
  author =	 {Mahdi Cheraghchi and Vasileios Nakos},
  title =	 {Combinatorial Group Testing Schemes with
                  Near-Optimal Decoding Time},
  booktitle =	 {Proceedings of the 61st Annual {IEEE} Symposium on
                  Foundations of Computer Science {(FOCS)}},
  year =	 2020,
  doi =		 {10.1109/FOCS46700.2020.00115},
  url_Link = {https://ieeexplore.ieee.org/document/9317982},
  url_Paper =	 {https://arxiv.org/abs/2006.08420},
  abstract =	 {In the long-studied problem of combinatorial group
                  testing, one is asked to detect a set of $k$
                  defective items out of a population of size $n$,
                  using $m \ll n$ disjunctive measurements. In the
                  non-adaptive setting, the most widely used
                  combinatorial objects are disjunct and list-disjunct
                  matrices, which define incidence matrices of test
                  schemes. Disjunct matrices allow the identification
                  of the exact set of defectives, whereas list
                  disjunct matrices identify a small superset of the
                  defectives.  Apart from the combinatorial
                  guarantees, it is often of key interest to equip
                  measurement designs with efficient decoding
                  algorithms. The most efficient decoders should run
                  in sublinear time in $n$, and ideally near-linear in
                  the number of measurements $m$.  In this work, we
                  give several constructions with an optimal number of
                  measurements and near-optimal decoding time for the
                  most fundamental group testing tasks, as well as for
                  central tasks in the compressed sensing and heavy
                  hitters literature. For many of those tasks, the
                  previous measurement-optimal constructions needed
                  time either quadratic in the number of measurements
                  or linear in the universe size.  Among our results
                  are the following: a construction of disjunct
                  matrices matching the best known construction in
                  terms of the number of rows $m$, but achieving
                  $O(m)$ decoding time.  a construction of list
                  disjunct matrices with the optimal $m=O(k
                  \log(n/k))$ number of rows and nearly linear
                  decoding time in $m$; error-tolerant variations of
                  the above constructions; a non-adaptive group
                  testing scheme for the "for-each" model with $m=O(k
                  \log n)$ measurements and $O(m)$ decoding time; a
                  streaming algorithm for the "for-all" version of the
                  heavy hitters problem in the strict turnstile model
                  with near-optimal query time, as well as a "list
                  decoding" variant obtaining also near-optimal update
                  time and $O(k\log(n/k))$ space usage; an
                  $\ell_2/\ell_2$ weak identification system for
                  compressed sensing with nearly optimal sample
                  complexity and nearly linear decoding time in the
                  sketch length.  Most of our results are obtained via
                  a clean and novel approach which avoids
                  list-recoverable codes or related complex techniques
                  which were present in almost every state-of-the-art
                  work on efficiently decodable constructions of such
                  objects.  }
}

Downloads: 0