Heterogeneity Aware Two-Stage Group Testing

Mohamed A. Attia, Wei Ting Chang, Ravi Tandon

Research output: Contribution to journalArticlepeer-review


Group testing refers to the process of testing pooled samples to reduce the total number of tests. Given the current pandemic, and the shortage of test supplies for COVID-19, group testing can play a critical role in time and cost efficient diagnostics. In many scenarios, samples collected from users are also accompanied with auxiliary information (such as demographics, history of exposure, onset of symptoms). Such auxiliary information may differ across patients, and is typically not considered while designing group testing algorithms. In this paper, we abstract such heterogeneity using a model where the population can be categorized into clusters with different prevalence rates. The main result of this work is to show that exploiting knowledge heterogeneity can further improve the efficiency of group testing. Motivated by the practical constraints and diagnostic considerations, we focus on two-stage group testing algorithms, where in the first stage, the goal is to detect as many negative samples by pooling, whereas the second stage involves individual testing to detect any remaining samples. For this class of algorithms, we prove that the gain in efficiency is related to the concavity of the number of tests as a function of the prevalence. We also show how one can choose the optimal pooling parameters for one of the algorithms in this class, namely, doubly constant pooling. We present lower bounds on the average number of tests as a function of the population heterogeneity profile, and also provide numerical results and comparisons.

Original languageEnglish (US)
Article number9472951
Pages (from-to)3977-3990
Number of pages14
JournalIEEE Transactions on Signal Processing
StatePublished - 2021
Externally publishedYes


  • Pooled testing
  • group testing
  • hypothesis testing

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering


Dive into the research topics of 'Heterogeneity Aware Two-Stage Group Testing'. Together they form a unique fingerprint.

Cite this