A class of i.p.p. codes with efficient identification
Authors: Alexander Barg and Gregory Kabatiansky
ABSTRACT
Let C be a code of length n over a q-ary alphabet.
An n-word y is called a descendant of a set of t codewords
x^1,...,x^t if y_i \in {x^1_i,...,x^t_i} for all i=1,...,n.
A code is said to have the t-identifying parent property (t-i.p.p.)
if for any n-word y that is a descendant of
at most t parents it is possible to identify at least one of them.
An explicit construction is presented of t-i.p.p. codes of
rate bounded away from zero, for which
identification can be accomplished with complexity poly(n).
DIMACS Home Page