License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.41
URN: urn:nbn:de:0030-drops-94458
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9445/
Go to the corresponding LIPIcs Volume Portal

Guruswami, Venkatesan ; Xing, Chaoping ; Yuan, Chen

How Long Can Optimal Locally Repairable Codes Be?

pdf-format:
LIPIcs-APPROX-RANDOM-2018-41.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{guruswami_et_al:LIPIcs:2018:9445,
  author =	{Venkatesan Guruswami and Chaoping Xing and Chen Yuan},
  title =	{{How Long Can Optimal Locally Repairable Codes Bel}},
  booktitle =	{Approximation, Randomization, and Combinatorial  Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{41:1--41:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9445},
  URN =		{urn:nbn:de:0030-drops-94458},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.41},
  annote =	{Keywords: Locally Repairable Code, Singleton Bound}
}

Keywords: Locally Repairable Code, Singleton Bound
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Issue Date: 2018
Date of publication: 13.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI