Construction of optimal locally recoverable codes and connection with hypergraph
Locally recoverable codes are a class of block codes with an additional property called locality. A locally recoverable code with locality r can recover a symbol by reading at most r other symbols. Recently, it was discovered by several authors that a q-ary optimal locally recoverable code, i.e., a locally recoverable code achieving the Singleton-type bound, can have length much bigger than q + 1. In this paper, we present both the upper bound and the lower bound on the length of optimal locally recoverable codes. Our lower bound improves the best known result in  for all distance d ≥ 7. This result is built on the observation of the parity-check matrix equipped with the Vandermonde structure. It turns out that a parity-check matrix with the Vandermonde structure produces an optimal locally recoverable code if it satisfies a certain expansion property for subsets of Fq. To our surprise, this expansion property is then shown to be equivalent to a well-studied problem in extremal graph theory. Our upper bound is derived by an refined analysis of the arguments of Theorem 3.3 in .
|Keywords||Hypergraph, Locally repairable codes|
|Conference||International Colloquium on Automata, Languages and Programming|
Xing, C, & Yuan, C. (2019). Construction of optimal locally recoverable codes and connection with hypergraph. In Leibniz International Proceedings in Informatics, LIPIcs. doi:10.4230/LIPIcs.ICALP.2019.98