Superimposed Codes and Their Applications: Old Results in New Light

摘要

Superimposed codes, also known as cover-free families, disjunct matrices, strongly selective families (and, possibly, with different appellatives), were introduced in 1948 by Mooers as a tool for fast and efficient information retrieval in punched card systems. Since then, superimposed codes have found applications in a surprising variety of areas: compressed sensing, cryptography and data security, group testing, computational biology, multi-access communication, database theory, pattern matching, distributed computation, and circuit complexity, among the others. Owing to the importance of the different scenarios where superimposed codes find applications, and starting from the seminal work of Kautz and Singleton [1964], many researchers have tried to find efficient algorithms to construct good superimposed codes (and still try). In this talk, I will start from classic results in the area, revisit them in a new light, present a few recent results, and discuss novel variations of superimposed codes dictated by modern application scenarios.