Abstract: Consider the following challenge. Given a large population, we need to identify infected individuals but with a limited number of tests. We faced this challenge at a large scale during the last few years with COVID-19. One way to tackle this challenge (tracing back to Dorfman) is to test groups (i.e., subsets) of individuals together. Individuals in groups that test negative are declared negative without further testing; everyone else is individually tested. Doing so can save numerous tests when relatively few people are infected (since most groups will test negative). Even greater savings are possible by assigning each individual to more than one group.

A crucial question is: how to form the groups? There has been tremendous research and progress on this topic. Here, we focus on the problem of forming groups that are "balanced" in the sense that: (a) each group has the same number of individuals, (b) each individual is in the same number (say q) of groups, and (c) the intersection of every q groups has the same number of individuals. The need for balance comes from real-life considerations when implementing group testing in the lab. Balanced groups create more consistency in the grouping procedure (which makes it less error-prone) and they can help make the performance more even across the individuals.

In this talk, we propose a method (we call HYPER) for producing balanced groups. It produces balanced designs by using hypergraph factorization. We evaluate HYPER under a realistic COVID-19 simulation, and find that it matches or outperforms state-of-the-art alternatives across a broad range of testing-constrained settings. We also evaluate HYPER under a common theoretical model, and find that its performance for noiseless tests appears to be close in some settings to a recently discovered information-theoretic bound.

The contents of this talk are primarily based on the following paper:

• Group testing via hypergraph factorization applied to COVID-19. David Hong, Rounak Dey, Xihong Lin, Brian Cleary, Edgar Dobriban. Nature Communications, 2022. https://doi.org/10.1038/s41467-022-29389-z

Bio: David Hong completed his B.S. in ECE and mathematics at Duke University under the Benjamin N. Duke full scholarship. He completed his Ph.D. in EECS at the University of Michigan under the NSF Graduate Research Fellowship. He is now an NSF Mathematical Sciences Postdoctoral Fellow in the Department of Statistics and Data Science at the University of Pennsylvania.

His broad interests lie in the foundations of data science and include group testing as well as low-rank matrix and tensor methods for high-dimensional and heterogeneous data.

Zoom ID:92716427348; pw: 032264