Algorithms for Generating Cover-Free Families

Abstract

Cover-free families (CFFs) are a combinatorial design used in many applications, including group testing and cryptography such as encryption and signature schemes. A $d$-cover-free family, denoted $d$-CFF($t$,$n$), is a set system where the underlying set has $t$ elements, the set system has $n$ subsets, and no subset is contained in the union of any $d$ other subsets. When cover-free families are used in applications, it is generally desirable to maximize the number of subsets for a given set of underlying elements. These subsets correspond to samples in group testing, allowing more efficient testing schemes. Currently, there are no publicly available tables of cover-free families that show the best-known cover-free family for specific parameters. This creates a challenge when implementing applications using cover-free families, since there are a variety of sources and constructions for cover-free families that would be useful. Tables for other types of combinatorial designs are publicly available, such as covering arrays, and these tables provide useful information to researchers. In this thesis, we outline a selection of constructions of cover-free families, then create and implement algorithms to create tables of best-known cover-free families from these selected constructions. Our selection of direct constructions includes constructions from Sperner systems, packing designs, Reed-Solomon codes, and linear error correcting codes meeting the Gilbert-Varshamov bound constructed using the method of conditional probabilities. Our selection of recursive constructions include the Kronecker product, the Optimized Kronecker product, an additive construction, a doubling construction for $d=2$, and an extension-by-one construction, which create larger cover-free families from smaller ones. Using these selected constructions, we iterate over combinations of parameters for each construction to create tables of best-known cover-free families from these constructions. Furthermore, we design and implement a recursive algorithm to construct any chosen cover-free family in our tables. Our results include tables of cover-free families for $n$ up to $10$ trillion, and $d$ up to 25. The maximum $t$ appearing in any of our tables is $18,744$ for $d=25$.