On codes from hypergraphs.

DOI10.1016/J.EJC.2003.10.002MaRDI QIDQ1427432zbMATH OpenOpenAlexFDO

Authors Yonatan Bilu, Shlomo Hoory

Publication date 14 March 2004

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejc.2003.10.002

zbMATH Keywords

\(t\)-uniform hypergraphbinary codesexpander codeshypergraph theory

Mathematics Subject Classification ID

Hypergraphs (05C65) Combinatorial codes (94B25) Decoding (94B35)

Review text

Based on hypergraph theory, the authors propose a new family of binary codes. This family of codes generalizes a previous construction of expander codes to \(t\)-uniform hypergraphs. After the introduction Section 2 defines hypergraph codes and gives some properties of them. Section 3 describes the decoding algorithm and introduces the main theorems. The following sections give the proofs of these theorems. Some open problems are presented in section 4.

Recommendations

• scientific article; zbMATH DE number 2081133
• On graphs and codes
• Codes on Graphs: Fundamentals
• Codes on graphs: Recent progress
• Codes over hyperfields
• Codes over graphs
• A note on codegree problems for hypergraphs
• Publication:4502606
• Superimposed codes and hypergraphs containing no grids.
• Codes from incidence matrices of graphs

Cites work

• A recursive approach to low complexity codes
• Derandomized graph products
• Error exponents of expander codes
• Expander codes
• scientific article; zbMATH DE number 3487716 (Why is no real title available?)
• scientific article; zbMATH DE number 1250549 (Why is no real title available?)
• On expander codes
• Ramanujan graphs
• Relative expanders or weakly relatively Ramanujan graphs.
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(20)

• Weight distribution and decoding of codes on hypergraphs
• Decoding concatenated codes with inner convolutional codes
• Erasure correction and locality of hypergraph codes
• Sparse random tensors: concentration, regularization and applications
• 2-cancellative hypergraphs and codes
• Expander graphs and their applications
• Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
• scientific article; zbMATH DE number 720914 (Why is no real title available?)
• scientific article; zbMATH DE number 2081133 (Why is no real title available?)
• Hypergraph expanders of all uniformities from Cayley graphs
• Sparse hypergraphs with applications to coding theory
• Deterministic tensor completion with hypergraph expanders
• Superimposed codes and hypergraphs containing no grids.
• Asymptotically good homological error correcting codes
• Eigenvalues and linear quasirandom hypergraphs
• Construction of storage codes of rate approaching one on triangle-free graphs
• Erasure list-decodable codes and Turán hypercube problems
• The edge code of hypergraphs
• Nonbinary code-based graphs and applications
• Low-complexity error correction of Hamming-code-based LDPC codes

This page was built for publication: On codes from hypergraphs.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1427432)