On Optimal Superimposed Codes

Vladimir Lebedev

Institute for Problems of Information Transmission of the Russian Academy of Sciences

Abstract:

A (w,r) cover-free family is a family of subsets of a finite set such that no intersection of w members of the family is covered by a union of r others. A binary (w,r) superimposed code is the incidence matrix of such a family. Such a family also arises in cryptography as a concept of key distribution patterns. We developed a method of constructing superimposed codes and proved that some superimposed codes constructed in this
way are optimal.

Biography:

Vladimir Lebedev received the M.S. in Mathematics degree in mathematics from the Lomonosov State University, Moscow, Russia, in 1987, and the Ph.D. in Mathematics degree from the Moscow Institute of Electronics and Mathematics, Moscow, Russia, in 1996. Since 1996 he is Associate Professor at the Institute for Information Transmission Problems in Moscow. He was co-organizer of severals "Workshop on Algebraic and Combinatorial Coding Theory (ACC)" in Bulgaria and Russia. His main research activities are the development of non-adaptive group testing theory, the development of coding theory with feedback and the investigations of adaptive and non-adaptive combinatorial search models.