Povzetek: Superimposed codes represent the main tool for the efficient solution of several problems arising in compressed sensing, cryptography and data security, computational biology, multi-access communication, database theory, pattern matching, distributed colouring, and circuit complexity, among the others.
It has also become apparent that combinatorial structures strictly related to superimposed codes lie at the heart of an even vaster series of problems. E.g., selectors were instrumental to obtain fast broadcasting algorithms in radio networks, (p,k,n)-selectors were the basic tool for the first two-stage group testing algorithm with an information theoretic optimal number of tests, (d,\ell)- disjunct matrices were a crucial building block for the efficiently decodable non-adaptive group testing procedures.
We shall focus on a new combinatorial structure, superselectors, which encompasses and unifies all of the combinatorial structures mentioned above (and more). When appropriately instantiated, superselectors asymptotically match the best known constructions of (p,k,n)-selectors, (d, l)-list-disjunct matrices, monotone encodings and (k, alpha)-FUT families, MUT_k(r)-families for multi-access channel.