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. Journal articles
  4. Community-Aware Group Testing
 
research article

Community-Aware Group Testing

Nikolopoulos, Pavlos  
•
Srinivasavaradhan, Sundara Rajan
•
Guo, Tao
Show more
July 1, 2023
Ieee Transactions On Information Theory

Group testing is a technique that can reduce the number of tests needed to identify infected members in a population, by pooling together multiple diagnostic samples. Despite the variety and importance of prior results, traditional work on group testing has typically assumed independent infections. However, contagious diseases among humans, like SARS-CoV-2, have an important characteristic: infections are governed by community spread, and are therefore correlated. In this paper, we explore this observation and we argue that taking into account the community structure when testing can lead to significant savings in terms of the number of tests required to guarantee a given identification accuracy. To show that, we start with a simplistic (yet practical) infection model, where the entire population is organized in (possibly overlapping) communities and the infection probability of an individual depends on the communities (s)he participates in. Given this model, we compute new lower bounds on the number of tests for zero-error identification and design community-aware group testing algorithms that can be optimal under assumptions. Finally, we demonstrate significant benefits over traditional, community-agnostic group testing via simulations using both noiseless and noisy tests. Shorter versions of this article, which contained a subset of the material, were presented in the work by Nikolopoulos et al. (2021, 2021).

  • Details
  • Metrics
Type
research article
DOI
10.1109/TIT.2023.3250119
Web of Science ID

WOS:001017307000014

Author(s)
Nikolopoulos, Pavlos  
•
Srinivasavaradhan, Sundara Rajan
•
Guo, Tao
•
Fragouli, Christina  
•
Diggavi, Suhas N. N.  
Date Issued

2023-07-01

Publisher

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC

Published in
Ieee Transactions On Information Theory
Volume

69

Issue

7

Start page

4361

End page

4383

Subjects

Computer Science, Information Systems

•

Engineering, Electrical & Electronic

•

Computer Science

•

Engineering

•

coding

•

group testing

•

defective members

•

graphs

•

bounds

•

pools

Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LICOS  
ARNI  
Available on Infoscience
August 14, 2023
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/199767
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