New bounds on parent-identifying codes: The case of multiple parents

Noga Alon, Uri Stav

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


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 {x1, . . . ,x t} if yi, ∈ {xi1, . . . ,x it} for all i = 1, . . . , n. A code is said to have the Identifiable Parent Property of order t if, for any word of length n that is a descendant of at most t codewords (parents), it is possible to identify at least one of them. Let ft(n,q) be the maximum possible cardinality of such a code. We prove that for any t,n,q, (c1(t)q)n/s(t) < ft(n,q) < c2(t)q⌈n/s(t)⌉ where s(t) = ⌊(t/2 + 1)2⌋ - 1 and c1(t), c 2(t) are some functions of t. We also show some bounds and constructions for f3(5,q). f3(6,q), and f t,(n,q) when n < s(t).

Original languageEnglish (US)
Pages (from-to)795-807
Number of pages13
JournalCombinatorics Probability and Computing
Issue number6
StatePublished - Nov 2004
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'New bounds on parent-identifying codes: The case of multiple parents'. Together they form a unique fingerprint.

Cite this