Combinatorial Alphabet-Dependent Bounds for Locally Recoverable Codes

DOI10.1109/TIT.2018.2800042MaRDI QIDQ5375529zbMATH OpenOpenAlexFDO

Authors Abhishek Agarwal, Alexander Barg, Sihuang Hu, Arya Mazumdar, Itzhak Tamo

Publication date 14 September 2018

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Bounds on codes (94B65)

Abstract: Locally recoverable (LRC) codes have recently been a focus point of research in coding theory due to their theoretical appeal and applications in distributed storage systems. In an LRC code, any erased symbol of a codeword can be recovered by accessing only a small number of other symbols. For LRC codes over a small alphabet (such as binary), the optimal rate-distance trade-off is unknown. We present several new combinatorial bounds on LRC codes including the locality-aware sphere packing and Plotkin bounds. We also develop an approach to linear programming (LP) bounds on LRC codes. The resulting LP bound gives better estimates in examples than the other upper bounds known in the literature. Further, we provide the tightest known upper bound on the rate of linear LRC codes with a given relative distance, an improvement over the previous best known bounds.

Cited in

(16)

• Locally recoverable \(J\)-affine variety codes
• Locally recoverable codes from algebraic curves with separated variables
• Linear programming bounds for distributed storage codes
• Constructions of optimal locally recoverable codes via Dickson polynomials
• The complete hierarchical locality of the punctured simplex code
• Perfect LRCs and k-optimal LRCs
• Optimal binary linear locally repairable codes with disjoint repair groups
• Codes for Distributed Storage
• New upper bounds and constructions of multi-erasure locally recoverable codes
• Singleton-optimal LRCs and perfect LRCs via cyclic and constacyclic codes
• Constacyclic locally recoverable codes from their duals
• Bounds on the size of (r,)-locally repairable codes for fixed values q and d
• Hull dimension of optimal binary LRCs with availability
• LRCS: duality, LP bounds, and field size
• Two classes of locally recoverable codes from cyclic codes with low locality
• Optimal RS-like LRC codes of arbitrary length

This page was built for publication: Combinatorial Alphabet-Dependent Bounds for Locally Recoverable Codes

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