A hypergraph approach to the identifying parent property: The case of multiple parents

Alexander Barg, Gérard Cohen, Sylvia Encheva, Gregory Kabatiansky, Gilles Zémor

Research output: Contribution to journalArticlepeer-review

64 Citations (Scopus)

Abstract

Let C be a code of length n over an alphabet of q letters. An n-word y is called a descendant of a set of t codewords x1, . . . , xt if yz ∈ {1i, . . . , xti} for all i = 1, . . , n. A code is said to have the t-identifying 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 ≤ q - 1 there exist sequences of such codes with asymptotically nonvanishing rate.

Original languageEnglish
Pages (from-to)423-431
Number of pages9
JournalSIAM Journal on Discrete Mathematics
Volume14
Issue number3
DOIs
Publication statusPublished - May 2001
Externally publishedYes

Keywords

  • Error-correcting codes
  • Helly property
  • Identifying parent property

Fingerprint

Dive into the research topics of 'A hypergraph approach to the identifying parent property: The case of multiple parents'. Together they form a unique fingerprint.

Cite this