FR2.R6.2

Group Testing with General Correlation Using Hypergraphs

Hesam Nikpey, Saswati Sarkar, Shirin Saeedi Bidokhti, University of Pennsylvania, United States

Session:
Group Testing 2

Track:
17: Group Testing

Location:
Sigma/Delta

Presentation Time:
Fri, 12 Jul, 11:50 - 12:10

Session Chair:
Soheil Mohajer, University of Minnesota
Abstract
Group testing, a problem with applications in various fields, traditionally assumes independent node states. Recent research, however, focuses on real-world scenarios that often involve correlations among nodes, challenging the simplifying assumptions made in existing models. In this work, we consider a comprehensive model for arbitrary statistical correlation among node states. To capture and leverage these correlations effectively, we model the problem by hypergraphs inspired by \cite{gonen2022group}. We establish that arbitrary correlations among nodes can be represented as a hypergraph with a probability distribution over its edges, and designed a novel greedy algorithm capable of conducting informative tests and dynamically updating the distribution. We analyze its performance and give theoretical guarantees on the number of tests that depend solely on the entropy of the underlying probability distribution and the average number of infections. We later compare how this algorithm performs on the prior correlation models introduced.
Resources