On finding the largest minimum distance of locally recoverable codes: A graph theory approach.

The [ n , k , r ] -Locally recoverable codes (LRC) studied in this work are a well-studied family of [ n , k ] linear codes for which the value of each symbol can be recovered by a linear combination of at most r other symbols. In this paper, we study the LMD problem, which is to find the largest possible minimum distance of [ n , k , r ] -LRCs, denoted by D (n , k , r). LMD can be approximated within an additive term of one—it is known that D (n , k , r) is equal to either d ⁎ or d ⁎ − 1 , where d ⁎ = n − k − ⌈ k r ⌉ + 2. Moreover, for a range of parameters, it is known precisely whether the distance D (n , k , r) is d ⁎ or d ⁎ − 1. However, the problem is still open despite a significant effort. In this work, we convert LMD to an equivalent simply-stated problem in graph theory. Using this conversion, we show that an instance of LMD is at least as hard as computing the size of a maximal graph of high girth, a hard problem in extremal graph theory. This is an evidence that LMD—although can be approximated within an additive term of one—is hard to solve in general. As a positive result, thanks to the conversion and the exiting results in extremal graph theory, we solve LMD for a range of code parameters that has not been solved before. [ABSTRACT FROM AUTHOR]