Construction of optimal locally recoverable codes and connection with hypergraph

DOI10.4230/LIPICS.ICALP.2019.98arXiv1811.09142MaRDI QIDQ6310084FDOQ6310084

Publication date: 22 November 2018

Abstract: Recently, it was discovered by several authors that a

q

-ary optimal locally recoverable code, i.e., a locally recoverable code archiving the Singleton-type bound, can have length much bigger than

q + 1

. This is quite different from the classical

q

-ary MDS codes where it is conjectured that the code length is upper bounded by

q + 1

(or

q + 2

for some special case). This discovery inspired some recent studies on length of an optimal locally recoverable code. It was shown in cite{LXY} that a

q

-ary optimal locally recoverable code is unbounded for

d = 3, 4

. Soon after, it was proved that a

q

-ary optimal locally recoverable code with distance

d

and locality

r

can have length

O m e g a_{d, r} (q^{1 + 1 / l f l o o r (d - 3) / 2 f l o o r})

. Recently, an explicit construction of

q

-ary optimal locally recoverable codes for distance

d = 5, 6

was given in cite{J18} and cite{BCGLP}. In this paper, we further investigate construction optimal locally recoverable codes along the line of using parity-check matrices. Inspired by classical Reed-Solomon codes and cite{J18}, we equip parity-check matrices with the Vandermond structure. It is turns out that a parity-check matrix with the Vandermond structure produces an optimal locally recoverable code must obey certain disjoint property for subsets of

m a t h b b F_{q}

. To our surprise, this disjoint condition is equivalent to a well-studied problem in extremal graph theory. With the help of extremal graph theory, we succeed to improve all of the best known results in cite{GXY} for

d g e q 7

. In addition, for

d = 6

, we are able to remove the constraint required in cite{J18} that

q

is even.

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

This page was built for publication: Construction of optimal locally recoverable codes and connection with hypergraph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6310084)