On coset leader graphs of structured linear codes

DOI10.1007/S00454-019-00129-3MaRDI QIDQ1985294zbMATH OpenOpenAlexFDO

Authors Eran Iceland, Alex Samorodnitsky

Publication date 7 April 2020

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.01184

zbMATH Keywords

linear codeslocally correctable codesdiscrete curvature

Mathematics Subject Classification ID

Linear codes (general theory) (94B05)

Abstract: We suggest a new approach to obtain bounds on locally correctable and some locally testable binary linear codes, by arguing that these codes (or their subcodes) have coset leader graphs with high discrete Ricci curvature. The bounds we obtain for locally correctable codes are worse than the best known bounds obtained using quantum information theory, but are better than those obtained using other methods, such as the "usual" information theory. (We remark that our methods are completely elementary.) The bounds we obtain for a family of locally testable codes improve the best known bounds.

Recommendations

• On Coset Leader Graphs of LDPC Codes
• On the weight distribution of the coset leaders of constacyclic codes
• Computing coset leaders and leader codewords of binary codes
• On the Grassmann graph of linear codes
• The extended coset leader weight enumerator of a twisted cubic code
• The graphs of non-degenerate linear codes
• On the PAPR of cosets of linear codes
• On the Weight Distributions of Cosets of a Linear Code
• On the weight distribution of the coset leaders of the first-order Reed - Muller code (Corresp.)
• Linear codes over signed graphs

Cites work

• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 1250549 (Why is no real title available?)
• scientific article; zbMATH DE number 1024657 (Why is no real title available?)
• scientific article; zbMATH DE number 848093 (Why is no real title available?)
• A curved Brunn-Minkowski inequality on the discrete hypercube, or: what is the Ricci curvature of the discrete hypercube?
• A quadratic lower bound for three-query linear locally decodable codes over any field
• Alexandrov meets Lott-Villani-Sturm
• Breaking the quadratic barrier for 3-LCC's over the reals
• Dense locally testable codes cannot have constant rate and distance
• Discrete curvature and abelian groups
• Exponential lower bound for 2-query locally decodable codes via a quantum argument
• Generalized Alon--Boppana Theorems and Error-Correcting Codes
• Li-Yau inequality on graphs
• Locally testable vs. locally decodable codes
• Lower bounds for linear locally decodable codes and private information retrieval
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator
• On the efficiency of local decoding procedures for error-correcting codes
• Ricci curvature and eigenvalue estimate on locally finite graphs
• Ricci curvature of Markov chains on metric spaces
• Towards lower bounds on locally testable codes via density arguments

Cited in

(5)

• Spanoids -- an abstraction of spanning structures, and a barrier for LCCs
• Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs
• On the computation of coset leaders with high Hamming weight.
• On Coset Leader Graphs of LDPC Codes
• Locally testable codes and Cayley graphs

This page was built for publication: On coset leader graphs of structured linear codes

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