Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/89385
Title: How long can optimal locally repairable codes be?
Authors: Guruswami, Venkatesan
Xing, Chaoping
Yuan, Chen
Keywords: DRNTU::Science::Mathematics
Locally Repairable Code
Singleton Bound
Issue Date: 2018
Source: Guruswami, V., Xing, C., & Yuan, C. (2018). How long can optimal locally repairable codes be?. Leibniz International Proceedings in Informatics, 116, 41-. doi:10.4230/LIPIcs.APPROX-RANDOM.2018.41
Series/Report no.: Leibniz International Proceedings in Informatics
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 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 d >=slant 5, 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 Omega_{d,r}(q^{1+1/floor[(d-3)/2]}) when d <=slant r+2. Our bounds match when d=5, pinning down n=Theta(q^2) as the asymptotically largest length of an optimal LRC for this case.
URI: https://hdl.handle.net/10356/89385
http://hdl.handle.net/10220/46213
DOI: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.41
Rights: © 2018 Venkatesan Guruswami, Chaoping Xing, and Chen Yuan; licensed under Creative Commons License CC-BY.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
How Long Can Optimal Locally Repairable Codes Be.pdf494.92 kBAdobe PDFThumbnail
View/Open

Google ScholarTM

Check

Altmetric

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.