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. Improved Constructions for Non-adaptive Threshold Group Testing
 
conference paper

Improved Constructions for Non-adaptive Threshold Group Testing

Cheraghchi, Mahdi
2010
Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP)
37th International Colloquium on Automata, Languages and Programming (ICALP)

The basic goal in combinatorial group testing is to identify a set of up to d defective items within a large population of size n >> d using a pooling strategy. Namely, the items can be grouped together in pools, and a single measurement would reveal whether there are one or more defectives in the pool. The threshold model is a generalization of this idea where a measurement returns positive if the number of defectives in the pool passes a fixed threshold u, negative if this number is below a fixed lower threshold L <= u, and may behave arbitrarily otherwise. We study non-adaptive threshold group testing (in a possibly noisy setting) and show that, for this problem, O(d^{g+2} (\log d) log(n/d)) measurements (where g := u-L) suffice to identify the defectives, and also present almost matching lower bounds. This significantly improves the previously known non-constructive) upper bound O(d^{u+1} log(n/d)). Moreover, we obtain a framework for explicit construction of measurement schemes using lossless condensers. The number of measurements resulting from this scheme is ideally bounded by O(d^{g+3} (\log d) \log n). Using state-of-the-art constructions of lossless condensers, however, we come up with explicit testing schemes with O(d^{g+3} (\log d) quasipoly(log n)) and O(d^{g+3+beta} poly(log n)) measurements, for arbitrary constant beta > 0.

  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-642-14165-2_47
Web of Science ID

WOS:000286345400047

Author(s)
Cheraghchi, Mahdi
Date Issued

2010

Publisher

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa

Published in
Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP)
Series title/Series vol.

Lecture Notes in Computer Science; 6198

Start page

552

End page

564

Subjects

algo_misc

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
ALGO  
Event nameEvent placeEvent date
37th International Colloquium on Automata, Languages and Programming (ICALP)

Bordeaux, France

July 5-10, 2010

Available on Infoscience
September 16, 2010
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/53712
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