pith. sign in

arxiv: 1907.05316 · v1 · pith:4TVGBSNMnew · submitted 2019-07-11 · 💻 cs.IT · math.IT

Computing sharp recovery structures for Locally Recoverable codes

Irene Marquez-Corbella , Edgar Martinez-Moro , Carlos Munuera This is my paper

Pith reviewed 2026-05-24 23:01 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords locally recoverable codesrecovery structureslinear codeslocalitydual distanceerror-correcting codesalgorithm
0
0 comments X

The pith

An algorithm computes the most concise recovery structure for any linear code and determines its locality and dual distance.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops an algorithm to compute a recovery structure for an arbitrary linear code that is as concise as possible, along with a method to realize the recovery of any single erased coordinate. This also yields the locality of the code, defined as the smallest size of such recovery sets, and the dual distance. A reader would care because it makes the property of local recoverability computable for any linear code rather than only for specially constructed ones. The algorithm's complexity is analyzed, with examples provided.

Core claim

We develop an algorithm that computes a recovery structure as concise as possible for an arbitrary linear code C and a recovery method that realizes it. This algorithm also provides the locality and the dual distance of C. Complexity issues are studied as well.

What carries the argument

The algorithm that computes minimal recovery structures for linear codes and the associated recovery methods that realize them.

Load-bearing premise

That a concise recovery structure and a realizing recovery method exist for any linear code and can be found by a finite algorithm.

What would settle it

A linear code for which the algorithm fails to output a recovery structure whose size matches the actual smallest possible sets needed to recover every single erasure.

read the original abstract

A locally recoverable code is an error-correcting code such that any erasure in a single coordinate of a codeword can be recovered from a small subset of other coordinates. In this article we develop an algorithm that computes a recovery structure as concise posible for an arbitrary linear code $\mathcal{C}$ and a recovery method that realizes it. This algorithm also provides the locality and the dual distance of $\mathcal{C}$. Complexity issues are studied as well. Several examples are included.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper develops an algorithm that, for an arbitrary linear code C, computes a recovery structure of minimal size together with a realizing recovery method; the algorithm also outputs the locality and dual distance of C. Complexity of the procedure is analyzed and several examples are provided.

Significance. If the algorithm is correct and its complexity bounds hold, the result supplies a concrete computational procedure for determining sharp locality parameters and recovery structures for any linear code. This is a useful addition to the toolkit for constructing and analyzing locally recoverable codes, especially when explicit constructions are unavailable.

minor comments (3)
  1. Abstract: 'concise posible' should read 'concise possible'.
  2. The manuscript should clarify in §3 or §4 whether the algorithm runs in time polynomial in the code length or requires enumeration of subsets; the stated complexity bound needs an explicit big-O expression tied to the parameters n, k, d.
  3. Notation for the recovery structure (Definition 2.3) and the realizing method should be cross-referenced consistently with the output of Algorithm 1.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and recommendation of minor revision. No major comments were listed in the report.

Circularity Check

0 steps flagged

No significant circularity; algorithmic contribution is self-contained

full rationale

The paper claims to develop and analyze a finite algorithm that, for any linear code, outputs a minimal recovery structure, a realizing recovery method, the locality, and the dual distance. This is a constructive existence claim satisfied by exhibiting the algorithm and studying its complexity, with no equations, fitted parameters, predictions, or self-citations invoked as load-bearing premises. The abstract and description contain no derivation chain that reduces to its own inputs by construction. The contribution is therefore independent of the patterns that would indicate circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review; no free parameters, invented entities, or non-standard axioms are mentioned. Standard linear algebra over finite fields is presupposed but not detailed.

axioms (1)
  • standard math Linear codes are vector spaces over finite fields
    Implicit in the definition of linear code C used throughout the abstract.

pith-pipeline@v0.9.0 · 5595 in / 1105 out tokens · 43108 ms · 2026-05-24T23:01:35.589608+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages · 1 internal anchor

  1. [1]

    Ashikhmin and A

    A. Ashikhmin and A. Barg, Minimal vectors in linear codes, IEEE Tra ns. Inform. Theory 44 (1998), no. 5, 2010–2017

    work page 1998

  2. [2]

    E. R. Berlekamp, R. J. McEliece, and H. C. A. van Tilborg, On the inh erent intractability of certain coding problems, IEEE Trans. Information Theory, IT-24(3):384 –386, 1978

    work page 1978

  3. [3]

    Bertilsson and I

    M. Bertilsson and I. Ingemarsson, A Construction of Practical Secret Sharing Schemes using Linear Block Codes, in Advances in Cryptology - AUSCRYPT’92, vol. 718, 199 2, 67–79

    work page

  4. [4]

    Blaum and S.R

    M. Blaum and S.R. Hetzler, Integrated interleaved codes as locally recoverable codes: properties and performance, Int. J. Inf. Coding Theory 3(4) (2016), 324–344

    work page 2016

  5. [5]

    A.; Fitzpatrick, P.; M artnez-Moro, E

    Borges-Quintana, M.; Borges-Trenard, M. A.; Fitzpatrick, P.; M artnez-Moro, E. Gr¨ obner bases and combinatorics for binary codes. Appl. Algebra Engrg. Comm. Compu t. 19 (2008), no. 5, 393–411

    work page 2008

  6. [6]

    Faldum and W

    A. Faldum and W. Willems, Codes of small defect, Designs, Codes an d Cryptography 10 (1997), 341–350

    work page 1997

  7. [7]

    Gopalan, C

    P. Gopalan, C. Huang, H. Simitci and S. Yekhanin, On the locality of codeword symbols, IEEE Transactions on Information Theory 58(11) (2012), 6925–6934

    work page 2012

  8. [8]

    J. D. Horton, A polynomial-time algorithm to find the shortest cyc le basis of a graph, SIAM J. Comput. 16(2) (1987), 358–366

    work page 1987

  9. [9]

    L. Jin, L. Ma and C. Xing, Construction of optimal locally repairable codes via automorphism groups of rational function fields, arXiv:1710.09638 (2017). COMPUTING SHARP RECOVERY STRUCTURES FOR LRC CODES 13

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  10. [10]

    M´ arquez-Corbella, E

    I. M´ arquez-Corbella, E. Mart ´ ınez-Moro and E. Su´ arez-Canedo, On the ideal associated to a linear code, Adv. Math. Commun. 10(2) (2016), 229–254

    work page 2016

  11. [11]

    Massey, Minimal Codewords and Secret Sharing, in Proceed ings of the 6th Joint Swedish-Russian International Workshop on Information Theory, 1993, 276–279

    J.L. Massey, Minimal Codewords and Secret Sharing, in Proceed ings of the 6th Joint Swedish-Russian International Workshop on Information Theory, 1993, 276–279

    work page 1993

  12. [12]

    Database for optimal parameters of ( t, m, s)-nets, ( t, s)-sequences, orthogonal arrays, linear codes and OOAs

    MinT. Database for optimal parameters of ( t, m, s)-nets, ( t, s)-sequences, orthogonal arrays, linear codes and OOAs. Online available at http://mint.sbg.ac.at/index.php

    work page

  13. [13]

    D. S. Papailiopoulos and A. G. Dimakis, Locally repairable codes, IE EE Trans. Inf. Theory 60(10) (2014), 5843–5855

    work page 2014

  14. [14]

    Online available at http://www.sagemath.org

    SageMath, the Sage Mathematics Software System (Version 8 .4), The Sage Developers, 2018. Online available at http://www.sagemath.org

    work page 2018

  15. [15]

    A. S. Rawat, O. O. Koyluoglu, N. Silberstein, and S. Vishwanath, Optimal locally repairable and secure codes for distributed storage systems, IEEE Trans. Inf . Theory, 60(1) (2014), 212–236

    work page 2014

  16. [16]

    Tamo and A

    I. Tamo and A. Barg, A family of optimal locally recoverable codes , IEEE Trans. Inform. Theory, vol. 60(8) (2014), 4661–4676

    work page 2014

  17. [17]

    I. Tamo, A. Barg, S. Goparaju, and R. Calderbank, Cyclic LRC c odes and their subfield subcodes, in Proc. IEEE Int. Sympos. Inform. Theory, Hong Kong, 2015, 12 62–1266. Department of Mathematics, Statistics and O. Research, Uni versity of La Laguna, 38200 La Laguna , Tenerife, Spain E-mail address : imarquec@ull.es Institute of Mathematics, University of V...

    work page 2015