Combinatorial group testing (CGT) is used to identify defective items from a set of items by grouping them together and performing a small number of tests on the groups. Recently, group testing has been used to design efficient COVID-19 testing, so that resources are saved while still identifying all infected individuals. Due to test waiting times, a focus is given to non-adaptive CGT, where groups are designed a priori and all tests can be done in parallel. The design of the groups can be done using Cover-Free Families (CFFs). We are interested in applications where the defective items are more likely to appear together in predictable subsets of items. For instance, it is reasonable to assume that infectious diseases show up in clusters of individuals with high contact. This structure can be modelled using hypergraphs, where vertices are items to be tested and edges represent clusters containing high contacts. In this work, we give constructions of what we call structure-aware CFF, which uses the structure of the underlying hypergraph. We revisit old CFF constructions, boosting the number of defectives they can identify by taking the hypergraph structure into account. We also provide new constructions based on hypergraph parameters.

Bio: Thaís has been a professor of Computer Science at the Federal University of Santa Catarina (Brazil) since 2021. She received her Ph.D. in Computer Science in 2019 at the University of Ottawa and held a Postdoctoral Fellow position at the Department of Mathematics at Simon Fraser University from November 2019 to January 2021. Before that, she completed her bachelor's and master's degree in Computer Science in Brazil. She is interested in the overlap between combinatorial designs and cryptography and currently works with cover-free families, digital signatures, and their applications in practical problems.