MATH Seminar
| Title: Superimposed Codes |
|---|
| Colloquium: N/A |
| Speaker: Zoltan Furedi of University of Illinois at Urbana-Champaign and Renyi Institute of Mathematics of the Hungarian Academy of Sciences |
| Contact: Andrzej Rucinski, andrzej@mathcs.emory.edu |
| Date: 2013-02-04 at 4:00PM |
| Venue: MSC W303 |
| Download Flyer |
| Abstract: There are many instances in Coding Theory when codewords must be restored from partial information, like defected data (error correcting codes), or some superposition of the strings. These lead to superimposed codes, a close relative of group testing problems. There are lots of versions and related problems, like Sidon sets, sum-free sets, union-free families, locally thin families, cover-free codes and families, etc. We discuss two cases {\it cancellative} and {\it union-free} codes. A family of sets $\mathcal F$ (and the corresponding code of 0-1 vectors) is called {\bf union-free} if $A\cup B\neq C\cup D$ and $A,B,C,D\in \mathcal F$ imply $\{ A,B\}=\{ C, D \}$. $\mathcal F$ is called $t$-{\bf cancellative} if for all distict $t+2$ members $A_1, \dots, A_t$ and $B,C\in \mathcal F$ $$A_1\cup\dots \cup A_t\cup B \neq A_1\cup \dots A_t \cup C. $$ Let $c_t(n)$ be the size of the largest $t$-cancellative code on $n$ elements. We significantly improve the previous upper bounds of K\"orner and Sinaimeri, e.g., we show $c_2(n)\leq 2^{0.322n}$ (for $n> n_0$). We introduce a method to deal with such problems, namely we first investigate the constant weight case (i.e., uniform hypergraphs). |
See All Seminars