How Long Can Optimal Locally Repairable Codes Be?

DOI10.1109/TIT.2019.2891765MaRDI QIDQ5224022zbMATH OpenOpenAlexFDO

Authors Chaoping Xing, Chen Yuan, Venkatesan Guruswami

Publication date 19 July 2019

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

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

Mathematics Subject Classification ID

Bounds on codes (94B65)

Abstract: A locally repairable code (LRC) with locality $r$ allows for the recovery of any erased codeword symbol using only $r$ other codeword symbols. A Singleton-type bound dictates the best possible trade-off between the dimension and distance of LRCs --- an LRC attaining this trade-off is deemed emph{optimal}. Such optimal LRCs have been constructed over alphabets growing linearly in the block length. Unlike the classical Singleton bound, however, it was not known if such a linear growth in the alphabet size is necessary, or for that matter even if the alphabet needs to grow at all with the block length. Indeed, for small code distances $3,4$, arbitrarily long optimal LRCs were known over fixed alphabets. Here, we prove that for distances $dge5$, the code length $n$ of an optimal LRC over an alphabet of size $q$ must be at most roughly $O(d{q}^3)$. For the case $d=5$, our upper bound is $O(q^2)$. We complement these bounds by showing the existence of optimal LRCs of length $Omeg{a}_{d,r}(q^{1+1/lfloor(d-3)/2floor})$ when $dler+2$. These bounds match when $d=5$, thus pinning down $n=Theta(q^2)$ as the asymptotically largest length of an optimal LRC for this case.

Cited in

(31)

• Locally recoverable \(J\)-affine variety codes
• Optimal cyclic locally repairable codes with unbounded length from their zeros
• Optimal cyclic \((r, \delta )\) locally repairable codes with unbounded length
• On binary locally repairable codes with distance four
• Perfect LRCs and k-optimal LRCs
• Optimal quaternary \((r,\delta)\)-locally recoverable codes: their structures and complete classification
• scientific article; zbMATH DE number 7378653 (Why is no real title available?)
• Relaxed locally correctable codes
• Codes for Distributed Storage
• Codes in the sum-rank metric: fundamentals and applications
• A characterization of optimal locally repairable codes
• Singleton-optimal LRCs and perfect LRCs via cyclic and constacyclic codes
• A characterization of optimal constacyclic locally repairable codes
• Optimal binary and ternary locally repairable codes with minimum distance 6
• On Singleton-type bound of locally repairable codes
• Constacyclic locally recoverable codes from their duals
• Locally repairable codes with multiple repair sets based on packings of block size 4
• Optimal (r, )-LRCs from monomial-Cartesian codes and their subfield-subcodes
• Optimal ternary locally repairable codes
• On information-theoretic secure multiparty computation with local repairability
• Optimal (2, ) locally repairable codes via punctured simplex codes
• Easy repair via codes with simplex locality
• A class of locally recoverable codes over finite chain rings
• Bounds on the size of (r,)-locally repairable codes for fixed values q and d
• Introducing locality in some generalized AG codes
• Optimal locally repairable codes with multiple repair sets based on 2-regular packings
• Optimal array codes with hierarchical locality
• LRCS: duality, LP bounds, and field size
• Optimal quantum (r, )-locally repairable codes via classical ones
• Cyclic (r, ) locally recoverable codes from their constacyclic and negacyclic subcodes
• Optimal RS-like LRC codes of arbitrary length

This page was built for publication: How Long Can Optimal Locally Repairable Codes Be?

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