Sparsity-Constrained Community-Based Group Testing
<|reference_start|>Sparsity-Constrained Community-Based Group Testing: In this work, we consider the sparsity-constrained community-based group testing problem, where the population follows a community structure. In particular, the community consists of $F$ families, each with $M$ members. A number $k_f$ out of the $F$ families are infected, and a family is said to be infected if $k_m$ out of its $M$ members are infected. Furthermore, the sparsity constraint allows at most $\rho_T$ individuals to be grouped in each test. For this sparsity-constrained community model, we propose a probabilistic group testing algorithm that can identify the infected population with a vanishing probability of error and we provide an upper-bound on the number of tests. When $k_m = \Theta(M)$ and $M \gg \log(FM)$, our bound outperforms the existing sparsity-constrained group testing results trivially applied to the community model. If the sparsity constraint is relaxed, our achievable bound reduces to existing bounds for community-based group testing. Moreover, our scheme can also be applied to the classical dilution model, where it outperforms existing noise-level-independent schemes in the literature.<|reference_end|>
@article{jain2024sparsity-constrained,
    title={Sparsity-Constrained Community-Based Group Testing},
    author={Sarthak Jain, Martina Cardone, Soheil Mohajer},
    journal={arXiv preprint arXiv:2403.12419},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.12419},
    primaryClass={cs.IT math.IT}
}