Group testing is traditionally considered effective only in settings with low infection rates. However, recent models that capture correlation among individuals, especially through hypergraphs, raise the question of whether group testing can remain efficient even when the infection rate is high. In this work, we study adaptive group testing under correlated settings modeled by hypergraphs and show that group testing can remain effective by leveraging these correlations to infer node states. We first state our results for k-partite hypergraphs and graphs with pairwise bounded edge intersections, and provide testing strategies that remain efficient even when the average number of infections is high. We then focus on a special class of hypergraphs called hypertrees, where infections originate from a single seed, and show that the number of tests depends on the Hamiltonian number of the underlying tree and the entropy of the edges. We then generalize the results to two seeds infection and more general contact graphs.

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 [1]. We establish that arbitrary correlations among nodes can be represented as a hypergraph with a probability distribution over its edges, and design a novel greedy adaptive 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.

In applications of group testing in networks, e.g. identifying individuals who are infected by a disease spread over a network, exploiting correlation among network nodes provides fundamental opportunities in reducing the number of tests needed. We model and analyze group testing on n correlated nodes whose interactions are specified by a graph G. We model correlation through an edge-faulty random graph formed from G in which each edge is dropped with probability$1-r$, and in the newly formed graph, all nodes in the same component have the same state. We consider three classes of graphs: cycles and trees, d-regular graphs and stochastic block models or SBM, and obtain lower and upper bounds on the number of tests needed to identify the defective nodes. Roughly speaking, we use correlation among the states of the nodes to transform the problem into that of a smaller graph with independent node states. This enhancement is quantified through the ratio of the diminished node count to the overall count of nodes, n; thus, a lower ratio signifies superior performance. The lower bounds are derived by illustrating a strong dependence of the number of tests needed on the expected number of components. In this regard, we establish a new approximation for the distribution of component sizes in “d-regular trees” which may be of independent interest and leads to a lower bound on the expected number of components in d-regular graphs. The upper bounds are found by forming dense subgraphs in which nodes are more likely to be in the same state. When G is a cycle or tree, we show an improvement by a factor of$\log (1/r)$. For grid, a graph with almost$2n$edges, the improvement is by a factor of$(1-r) \log (1/r)$, indicating drastic improvement compared to trees. When G has a larger number of edges, as in SBM, the improvement can scale in n.

With the growth of big data in the past few decades, compression has become inseparable from data generation. The data generated daily across different platforms are correlated: friend networks on Facebook and Instagram, contact networks in subsequent days, and many more. This raises the question of compressing a dataset using another correlated dataset. For instance, can we compress the Facebook graph of friends when we know Instagram’s graph? This can be cast as the classical problem of source coding with side information, and the answer is known to be positive when the graphs are "labeled" and/or aligned, meaning we need to know the node corresponding to Jon Doe in both Facebook and Instagram graphs. The classical idea is to utilize joint typicality to decide whether two graphs are correlated or not. In practice, graphs are often not aligned and/or the labels are concealed to keep the identity of the users private. In these scenarios, classical ideas are no longer applicable as joint typicality highly depends on the ordering of sequences. In this work, we prove for the first time the existence of lossless graph compression schemes that utilize unlabeled side information and improve the compression rate. In order to do that, we design binning along with a novel testing criterion that relies on graph matching, the closely related quadratic assignment problem and its asymptotic properties.

In applications of group testing in networks, e.g. identifying individuals who are infected by a disease spread over a network, exploiting correlation among network nodes provides fundamental opportunities in reducing the number of tests needed. We model and analyze group testing on n correlated nodes whose interactions are specified by a graph G. We model correlation through an edge-faulty random graph formed from G in which each edge is dropped with probability 1−r, and all nodes in the same component have the same state.We consider three classes of graphs: cycles and trees, d-regular graphs, and stochastic block models or SBM, and obtain lower and upper bounds on the number of tests needed to identify the defective nodes. Our results are expressed in terms of the number of tests needed when the nodes are independent and they are in terms of n, r, and the target error. In particular, we quantify the fundamental improvements that exploiting correlation offers by the ratio between the total number of nodes n and the equivalent number of independent nodes in a classic group testing algorithm.The lower bounds are derived by illustrating a strong dependence of the number of tests needed on the expected number of components. In this regard, we establish a new approximation for the distribution of component sizes in "d-regular trees" which may be of independent interest and leads to a lower bound on the expected number of components in d-regular graphs.The upper bounds are found by forming dense subgraphs in which nodes are more likely to be in the same state. When G is a cycle or tree, we show an improvement by a factor of log(1/r). For grid, a graph with almost 2n edges, the improvement is by a factor of (1 − r)log(1/r), indicating drastic improvement compared to trees. When G has a larger number of edges, as in SBM, the improvement can scale in n.

We give the first polynomial-time approximation scheme (PTAS) for the stochastic load balancing problem when the job sizes follow Poisson distributions. This improves upon the 2-approximation algorithm due to Goel and Indyk (FOCS'99). Moreover, our approximation scheme is an efficient PTAS that has a running time double exponential in $1/ε$ but nearly-linear in $n$, where $n$ is the number of jobs and $ε$ is the target error. Previously, a PTAS (not efficient) was only known for jobs that obey exponential distributions (Goel and Indyk, FOCS'99). Our algorithm relies on several probabilistic ingredients including some (seemingly) new results on scaling and the so-called "focusing effect" of maximum of Poisson random variables which might be of independent interest.