Codes with parent identifying property and digital fingerprinting codes: what is in between?
Professor Gregory Kabatyanskiy, Institute for Information Trnasmission Problems, RAS, Moscow
Friday 05 February 2010, 1300-1400
In this talk we prove initial results on the proportion of "mutated" coordinates that can be tolerated under the IPP property. The talk is based on a joint work with A. Barg, G.R. Blakley and C. Tavernier.
An n-word y over a finite alphabet is called a descendant of a set U of t words (called "parents") if each coordinate of y coincides with the same coordinate of at least one of these t words. A code C is said to have the t-identifying parent property (t-IPP) if for any word y that is a descendant of at most t parents belonging to the code it is possible to identify at least one of them. The existence of good t-i.p.p. codes is known from earlier works.
We introduce a strong version of this problem under which some of the coordinates in y can break away from the descent rule ("mutate") , i.e., can take arbitrary values from the alphabet, or become completely unreadable.