Raziskovalni matematični seminar - Arhiv
| 2024 | 2023 | 2022 | 2021 | 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.
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.
