Superimposed codes

Tuesday, February 14, 2012 - 3:45pm - 4:15pm
Keller 3-180
Zoltan Furedi (Hungarian Academy of Sciences (MTA))
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, unionfree families, locally thin families, cover-free codes and families, etc. We discuss two cases cancellative and union-free codes.

A family of sets Ƒ (and the corresponding code of 0-1 vectors) is called union-free if A ∪ B≠ C ∪ D and A,B,C,D ∈ F imply {A,B} = {C,D}. Ƒ is called t-cancellative if for all distict t + 2 members A1, … ,At and B,C ∈ Ƒ

A1 ∪ ... ∪ At ∪ B ≠ A1 ∪ … At ∪C:

Let ct(n) be the size of the largest t-cancellative code on n elements. We significantly improve the previous upper bounds of Körner and Sinaimeri, e.g., we show c2(n) ≤ 20:322n (for n > n0).
MSC Code: