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. How little does non-exact recovery help in group testing?
 
conference paper

How little does non-exact recovery help in group testing?

Scarlett, Jonathan  
•
Cevher, Volkan  orcid-logo
2017
2017 Ieee International Conference On Acoustics, Speech And Signal Processing (Icassp)
IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

We consider the group testing problem, in which one seeks to identify a subset of defective items within a larger set of items based on a number of tests. We characterize the information-theoretic performance limits in the presence of list decoding, in which the decoder may output a list containing more elements than the number of defectives, and the only requirement is that the true defective set is a subset of the list, or more generally, that their overlap exceeds a given threshold. We show that even under this highly relaxed criterion, in several scaling regimes the asymptotic number of tests is no smaller than the exact recovery setting. However, we also provide examples where a reduction is provably attained. We support our theoretical findings with numerical experiments.

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

GT_ICASSP.pdf

Access type

openaccess

Size

247.13 KB

Format

Adobe PDF

Checksum (MD5)

3a8645b0231eff22033e53798191239e

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