Univerza na Primorskem Fakulteta za matematiko, naravoslovje in informacijske tehnologije
SI | EN

Raziskovalni matematični seminar - Arhiv

2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010
1 2 3 4 5 6 7 8 9 10 11 12
22.11.2010. ob 10:00 Seminarska soba v Galebu
Predavatelj: dr. Ferdinando Cicalese, sa Univerze v Salernu (Università degli Studi di Salerno).
 
Naslov: Superselectors: Efficient Constructions and Applications

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.
 
We shall show some implementations of superselectors which provide optimal approximate group testing schemes and quasi-optimal additive group testing schemes.

8.11.2010. ob 10:00 Seminarska soba v Galebu
Predavatelj: dr.Istvan Kovacs
Naslov: Covering systems of finite abelian groups
 
Povzetek: A covering system of a finite group G is a set S of ordered pairs of its subgroups,

S = { (M1,L1), ..., (Mn,Ln) }, which satisfies the following axioms:
1. Mii for all i.
2. (L1\M1) U
… U (Ln\Mn) = G\{1}.
3. |L1 : M1| ∙…∙ |Ln: Mn| = |G|.
The covering system S is said to be regular if some Li=G.
In the talk we study the regularity of covering systems of finite abelian groups.