Computational complexity of ﬁnding code locality

Valinurov Denis Yurevich

Computational complexity of ﬁnding code locality

Valinurov D. Y.

Valinurov Denis Yurevich

graduate student, Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Chair of Mathematical Theory of Intellectual Systems

Published: 2023, vol. 27, issue 1, pp. 80–90

Download full text (In Russian)

Abstract

The locally recoverable codes (LRC codes) are linear codes with an important for applications property that every symbol of a codeword can be recovered from a small set of other symbols. The paper provides reductions from known decision problems of coding theory to the problem of checking such property and a proof for the NP-completeness of this problem for an arbitrary ﬁxed ﬁnite field.

Keywords: erasure coding, locally recoverable codes, NP-complete.

BibTeX

@article{IS-Valinurov2023,
  author  = {Valinurov, Denis Yurevich},
  title   = {{Computational complexity of ﬁnding code locality}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2023},
  volume  = {27},
  number  = {1},
  pages   = {80--90},
}

AMSBIB

\Bibitem{IS-Valinurov2023}
\by D.\,Y.~Valinurov
\paper Computational complexity of ﬁnding code locality
\jour Intelligent Systems. Theory and Applications
\yr 2023
\vol 27
\issue 1
\pages 80--90
\lang In Russian

Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue