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. Phase Transitions in Group Testing
 
conference paper

Phase Transitions in Group Testing

Scarlett, Jonathan  
•
Cevher, Volkan  orcid-logo
2016
Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
ACM-SIAM Symposium on Discrete Algorithms (SODA)

The group testing problem consists of determining a sparse subset of a set of items that are ``defective'' based on a set of possibly noisy tests, and arises in areas such as medical testing, fault detection, communication protocols, pattern matching, and database systems. We study the fundamental limits of any group testing procedure regardless of its computational complexity. In the noiseless case with the number of defective items $k$ scaling with the total number of items $p$ as $O(p^{\theta})$ ($\theta\in(0,1)$), we show that the probability of reconstruction error tends to one when $n \le k\log_2\frac{p}{k}(1+o(1))$, but vanishes when $n \ge c(\theta)k\log_2\frac{p}{k}(1+o(1))$, for some explicit constant $c(\theta)$. For $\theta \le \frac{1}{3}$, we show that $c(\theta) = 1$, thus providing an exact threshold on the required number measurements, i.e.~a phase transition, which was previously known only in the limit as $\theta \to 0$. Analogous necessary and sufficient conditions are derived for the noisy setting, and also for a relaxed partial recovery criterion.

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

GroupTesting_SODA_1.pdf

Access type

openaccess

Size

604.39 KB

Format

Adobe PDF

Checksum (MD5)

742f6df20ee8a89f0fe19a19eeddcbeb

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