Epidemics and testing

One of the most significant challenges when managing pandemics, such as implementing quarantines or re-opening society, is the need for large scale, reliable, and continual monitoring of the epidemic/pandemic. The central idea is how to explore ideas, inspired by coding, to use group testing/sensing to reduce the testing scale for given desired reliability.

Group testing pools together diagnostic samples to reduce the number of tests needed to identify infected members in a population. In particular, if in a population of n members we have a small fraction infected (say k << n members), we can identify the infected members with much fewer tests than n individual tests. Triggered by the need of widespread testing, such techniques are already being explored in the context of Covid-19.

The observation we make is that we can leverage a known community structure to make group testing more efficient. The work in group testing we know of, assumes “independent” infections, and ignores that an infection is governed by community spread; we argue that taking into account the community structure can lead to significant savings. As a use case, consider an apartment building consisting of families that have practiced social distancing; clearly there is a strong correlation on whether members of the same family are infected or not. Assume that the building management would like to test all members to enable access to common facilities. We asked, what is the most test-efficient way to do so. Our approach enlarges the regime where group testing can offer benefits over individual testing. We examine two different community structures where such benefits can be demonstrated both in theory as well as through belief propagation based decoding algorithms and numerics.