Weight distribution and decoding of codes on hypergraphs

Alexander Barg, Arya Mazumdar, Gilles Zémor

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


Codes on hypergraphs are an extension of the well-studied family of codes on bipartite graphs. Bilu and Hoory (2004) constructed an explicit family of codes on regular t-partite hypergraphs whose minimum distance im- proves earlier estimates of the distance of bipartite-graph codes. They also sug- gested a decoding algorithm for such codes and estimated its error-correcting capability. In this paper we study two aspects of hypergraph codes. First, we com- pute the weight enumerators of several ensembles of such codes, establishing conditions under which they attain the Gilbert-Varshamov bound and deriving estimates of their distance. In particular, we show that this bound is attained by codes constructed on a fixed bipartite graph with a large spectral gap. We also suggest a new decoding algorithm of hypergraph codes that corrects a constant fraction of errors, improving upon the algorithm of Bilu and Hoory.

Original languageEnglish (US)
Pages (from-to)433-450
Number of pages18
JournalAdvances in Mathematics of Communications
Issue number4
StatePublished - Nov 2008
Externally publishedYes


  • Codes on graphs
  • Decoding
  • Hypergraphs
  • Weight distribution


Dive into the research topics of 'Weight distribution and decoding of codes on hypergraphs'. Together they form a unique fingerprint.

Cite this