On coset leader graphs of structured linear codes

DOI10.1007/S00454-019-00129-3zbMATH Open1434.94086arXiv1802.01184OpenAlexW2971356367MaRDI QIDQ1985294FDOQ1985294

Eran Iceland, Alex Samorodnitsky

Publication date: 7 April 2020

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Ricci curvature of Markov chains on metric spaces
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator
• Ricci curvature and eigenvalue estimate on locally finite graphs
• Li-Yau inequality on graphs
• Alexandrov meets Lott-Villani-Sturm
• A Curved Brunn--Minkowski Inequality on the Discrete Hypercube, Or: What Is the Ricci Curvature of the Discrete Hypercube?
• Exponential lower bound for 2-query locally decodable codes via a quantum argument
• On the efficiency of local decoding procedures for error-correcting codes
• Locally Testable vs. Locally Decodable Codes
• Lower bounds for linear locally decodable codes and private information retrieval
• Towards lower bounds on locally testable codes via density arguments
• Breaking the quadratic barrier for 3-LCC's over the reals
• Title not available (Why is that?)
• Discrete curvature and abelian groups
• Generalized Alon--Boppana Theorems and Error-Correcting Codes
• A quadratic lower bound for three-query linear locally decodable codes over any field
• Dense Locally Testable Codes Cannot Have Constant Rate and Distance

Cited In (4)

• 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

   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 👍 👎

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)