DIMACS TR: 2000-20

A Hypergraph Approach to the Identifying Parent Property: the Case of Multiple Parents

Authors: A. Barg, G. Cohen, S. Encheva, G. Kabatiansky, G. Zemor


Let $C$ be a code of length $n$ over an alphabet of $q$ letters. A codeword $y$ is called a descendant of a set of $t$ codewords $ x^1,\dots,x^t$ if $y_i\in\{x^1_i,\dots,x^t_i\}$ for all $i=1,\dots,n.$ A code is said to have the identifiable parent property if for any $n$-word that is a descendant of at most $t$ parents it is possible to identify at least one of them. We prove that for any $t\le q-1$ there exist sequences of such codes with asymptotically nonvanishing rate.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-20.ps.gz
DIMACS Home Page