Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Near-Optimal Noisy Group Testing via Separate Decoding of Items
 
conference paper

Near-Optimal Noisy Group Testing via Separate Decoding of Items

Scarlett, Jonathan  
•
Cevher, Volkan  orcid-logo
June 17, 2018
Proceedings of the 2018 IEEE International Symposium on Information Theory (ISIT)
IEEE International Symposium on Information Theory

In this paper, we revisit an efficient algorithm for noisy group testing in which each item is decoded separately (Malyutov and Mateev, 1980), and develop novel performance guarantees via an information-theoretic framework for general noise models. For the noiseless and symmetric noise models, we find that the asymptotic number of tests required for vanishing error probability is within a factor log 2 ≈ 0.7 of the informationtheoretic optimum at low parsity levels, and that when a small fraction of incorrectly-decoded items is allowed, this guarantee extends to all sublinear sparsity levels. In many scaling regimes, these are the best known theoretical guarantees for any noisy group testing algorithm.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

Near-Oprimal Noisy.pdf

Type

Postprint

Version

Accepted version

Access type

openaccess

Size

337.37 KB

Format

Adobe PDF

Checksum (MD5)

0f3a5f1a54327ffd965c6ed99070825a

Loading...
Thumbnail Image
Name

Near-Optimal Noisy Group Testing via Separate Decoding of Items.pdf

Type

Publisher's Version

Version

Published version

Access type

openaccess

Size

313.26 KB

Format

Adobe PDF

Checksum (MD5)

077ddf0911827ea89f7966de47a5a40b

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés