DIMACS TR: 2002-36
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).
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-36.ps.gz
DIMACS Home Page