2026-07-27T09:00:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10674 2024-03-06T10:46:26Z ddc:004 open_access

Construction of Optimal Locally Recoverable Codes and Connection with Hypergraph Xing, Chaoping Yuan, Chen Locally Repairable Codes 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 [Yuan Luo et al., 2018] 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 F_q. 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 [Venkatesan Guruswami et al., 2018]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chaoping Xing and Chen Yuan 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.98 urn:nbn:de:0030-drops-106745 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.98 eng https://creativecommons.org/licenses/by/3.0/legalcode