Low-weight superimposed codes and their applications

A (k, n)-superimposed code is a well known and widely used combinatorial structure that can be represented by a t × n binary matrix such that for any k columns of the matrix and for any column c chosen among these k columns, there exists a row in correspondence of which column c has an entry equal to 1 and the remaining k-1 columns have entries equal to 0. Due to the many situations in which superimposed codes find applications, there is an abundant literature that studies the problem of constructing (k, n)-superimposed codes with a small number t of rows. Motivated by applications to conflict-free communication in multiple-access networks, group testing, and data security, we study the problem of constructing superimposed codes that have the additional constraints that the number of 1’s in each column of the matrix is constant, and equal to an input parameter w. Our results improve on the known literature in the area. We also extend our findings to other important combinatorial structures, like selectors.