Raziskovalni matematični seminar

V ponedeljek, 22. novembra 2010, bo ob 10. uri v seminarski sobi v Galebu, v okviru raziskovalnega matematičnega seminarja, predaval dr. Ferdinando Cicalese, sa Univerze v Salernu (Università degli Studi di Salerno).

Predavanje bo v Angleščini.

Vljudno vabljeni k udeležbi na predavanju!

 

Title: Superselectors: Efficient Constructions and Applications

Abstract: 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.

 

We shall show some implementations of superselectors which provide optimal approximate group testing schemes and quasi-optimal additive group testing schemes.