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
Type
conference paper
DOI
10.1109/ICASSP.2017.7953326
Web of Science ID

WOS:000414286206051

Author(s)
Scarlett, Jonathan  
Cevher, Volkan  orcid-logo
Date Issued

2017

Publisher

Ieee

Publisher place

New York

Published in
2017 Ieee International Conference On Acoustics, Speech And Signal Processing (Icassp)
ISBN of the book

978-1-5090-4117-6

Total of pages

5

Start page

6090

End page

6094

Subjects

Group testing

•

information-theoretic limits

•

partial recovery

•

list decoding

•

strong converse

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LIONS  
Event nameEvent placeEvent date
IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

New Orleans

March 2017

Available on Infoscience
February 10, 2017
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/134252
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