arxiv: 2605.09748 · v1 · submitted 2026-05-10 · 💻 cs.IT · math.IT

Recognition: no theorem link

Recovery Algorithms for Linear Batch Codes

Baran D\"uzg\"un , Henk D.L. Hollmann , Ago-Erik Riet , Vitaly Skachek , Vladislav Taranchuk

Authors on Pith no claims yet

Pith reviewed 2026-05-12 03:27 UTC · model grok-4.3

classification 💻 cs.IT math.IT

keywords batch codesrecovery algorithmslinear codesgraph-based codesorder hierarchybipartite graphsdistributed storage

0 comments

The pith

Linear batch codes with specific recovery algorithms admit a systematic order hierarchy among their types.

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

This paper conducts the first systematic investigation of linear batch codes classified according to the recovery algorithms they support. It introduces and compares various known and new algorithm types while establishing their order relations. The work begins with the simplest case of graph-based batch codes constructed from arbitrary bipartite graphs and generalizes earlier results on such constructions. Understanding these hierarchies matters for applications in distributed storage, where batch codes enable efficient recovery of multiple data blocks from failures. The classification helps identify which codes provide stronger or weaker recovery guarantees under different algorithmic constraints.

Core claim

We introduce and investigate various known and new types of recovery algorithms for linear batch codes and establish the order hierarchy among the corresponding types of batch codes. The simplest known recovery algorithms are those associated with graph-based batch codes. We investigate the resulting batch codes for arbitrary bipartite graphs, thereby generalizing some known results.

What carries the argument

The order hierarchy of recovery algorithm types for linear batch codes, with graph-based algorithms from arbitrary bipartite graphs as the base case.

If this is right

Batch codes can be systematically classified by the strength of the recovery algorithms they admit.
Graph-based batch codes extend to constructions from any bipartite graph rather than restricted families.
Higher types in the hierarchy provide strictly stronger recovery properties than lower types.
The hierarchy enables direct comparison between different families of batch codes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The ordering could be used to select batch codes matching specific recovery requirements in storage systems.
Similar hierarchy approaches might apply to nonlinear batch codes or other coding schemes with local recovery.

Load-bearing premise

The introduced recovery algorithm types admit a total or partial order hierarchy that holds for all linear batch codes.

What would settle it

A concrete linear batch code in which the recovery algorithm types violate the claimed order relations.

read the original abstract

Various types of recovery algorithms for batch codes have been investigated, such as asynchronous recovery or recovery as afforded by batch codes obtained from Almost Affinely Disjoint (AAD) families. In this paper, we offer the first systematic investigation of linear batch codes equipped with particular recovery algorithms. We introduce and investigate various known and new types of algorithms, and we investigate the order hierarchy of these types of batch codes. The simplest known recovery algorithms are those associated with graph-based batch codes. We investigate the resulting batch codes for arbitrary bipartite graphs, thereby generalizing some known results.

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

2 major / 2 minor

Summary. The manuscript offers the first systematic investigation of linear batch codes equipped with particular recovery algorithms. It introduces and investigates various known and new types of algorithms, and examines the order hierarchy among the corresponding classes of batch codes. It also generalizes known results on graph-based batch codes to arbitrary bipartite graphs.

Significance. If the hierarchy and generalizations hold, the work would organize the relationships among recovery mechanisms for batch codes, aiding selection of constructions for distributed storage applications. The extension of graph-based results to arbitrary bipartite graphs is a clear strength that broadens prior constructions without requiring additional regularity assumptions.

major comments (2)

[Abstract and the section defining the hierarchy] The central claim of a (partial or total) order hierarchy among recovery algorithm types is load-bearing, yet the abstract provides no proof sketches, counterexample checks, or explicit verification steps for the ordering relations. Without these, it is impossible to confirm whether the hierarchy holds for all linear batch codes or collapses under changes in finite-field characteristic or bipartite-graph girth.
[Sections introducing the algorithm types and their ordering] The definitions of recovery properties (via linear dependence or support conditions) must be shown to yield a consistent ordering independent of unstated restrictions on the underlying finite field or graph structure; if the ordering is only uniform under specific assumptions, the claimed generality of the hierarchy is at risk.

minor comments (2)

[Introduction] Clarify in the introduction exactly which prior results on graph-based batch codes are being generalized and cite the specific theorems being extended.
[Notation and definitions] Ensure consistent notation for the newly introduced algorithm types across definitions, theorems, and examples.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback and for recognizing the significance of our systematic investigation into recovery algorithms for linear batch codes, including the generalization to arbitrary bipartite graphs. We address each major comment below and indicate planned revisions where appropriate.

read point-by-point responses

Referee: [Abstract and the section defining the hierarchy] The central claim of a (partial or total) order hierarchy among recovery algorithm types is load-bearing, yet the abstract provides no proof sketches, counterexample checks, or explicit verification steps for the ordering relations. Without these, it is impossible to confirm whether the hierarchy holds for all linear batch codes or collapses under changes in finite-field characteristic or bipartite-graph girth.

Authors: The abstract is intended as a high-level summary and does not contain detailed proofs, which are instead developed in the sections defining the algorithm types and establishing the hierarchy. These sections prove the partial order using linear dependence relations and support conditions that hold over arbitrary finite fields (independent of characteristic) and for any bipartite graph (without girth assumptions). The arguments rely only on standard vector space properties and the definition of batch codes. To improve accessibility, we will revise the abstract to note that the hierarchy is established through explicit theorems and illustrative examples in the main text. revision: partial
Referee: [Sections introducing the algorithm types and their ordering] The definitions of recovery properties (via linear dependence or support conditions) must be shown to yield a consistent ordering independent of unstated restrictions on the underlying finite field or graph structure; if the ordering is only uniform under specific assumptions, the claimed generality of the hierarchy is at risk.

Authors: The definitions of the recovery properties are stated in full generality using linear dependence over any finite field and support conditions on the underlying vectors, with no additional restrictions on field characteristic or graph structure. The ordering relations are derived directly from these definitions via standard linear algebra arguments that apply uniformly, as shown in the relevant theorems. The generalization to arbitrary bipartite graphs is handled separately and does not impose regularity conditions such as girth. The manuscript already demonstrates this generality through the proofs; no hidden assumptions are present. revision: no

Circularity Check

0 steps flagged

No circularity: systematic classification of recovery algorithms builds on external priors without self-referential reductions

full rationale

The paper conducts a systematic investigation of linear batch codes with known and new recovery algorithm types (graph-based, asynchronous, AAD-derived) and their order hierarchy, generalizing prior graph-based results to arbitrary bipartite graphs. No self-definitional steps, fitted-input predictions, or load-bearing self-citations appear in the provided abstract or description; the hierarchy is framed as an independent classification result rather than a quantity derived from the paper's own inputs by construction. This matches the default non-circular outcome for classification and generalization work.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard definitions of linear codes and batch codes from prior literature; no new free parameters, invented entities, or ad-hoc axioms are indicated in the abstract.

axioms (2)

standard math Linear codes are vector spaces over finite fields with standard linearity properties
Central to defining linear batch codes and their recovery algorithms.
domain assumption Bipartite graphs induce valid batch code constructions via incidence structures
Used when generalizing graph-based batch codes to arbitrary bipartite graphs.

pith-pipeline@v0.9.0 · 5399 in / 1269 out tokens · 61754 ms · 2026-05-12T03:27:02.840362+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

[1]

Arikan, B

T. Arikan, B. D ¨uzg¨un, K. Otal, and F. ¨Ozbudak, “A New Construction of Asymptotically Optimal Almost Affinely Disjoint Spaces, Proc. ISIT 2023, pp. 282–285

work page 2023
[2]

Asratian, T.M.J

A. Asratian, T.M.J. Denley, and R. H ¨aggkvist, Bipartite Graphs and their Applications, Cambridge University Press, 1998

work page 1998
[3]

Conlon, “Graphs with few paths of prescribed length between any two vertices,“ Bull

D. Conlon, “Graphs with few paths of prescribed length between any two vertices,“ Bull. London Math. Soc., 51, 2019, pp. 1015–1021

work page 2019
[4]

Recovery algorithms for linear batch codes,

B. D ¨uzg¨un, H.D.L. Hollmann, A.-E. Riet, V . Skachek, and V . Taranchuk, “Recovery algorithms for linear batch codes,” arxiv 2026

work page 2026
[5]

New constructions of unbalanced{C 4, θ3,t}-free bipartite graphs,

B. D ¨uzg¨un, A.-E. Riet, and V . Taranchuk, “New constructions of unbalanced{C 4, θ3,t}-free bipartite graphs,” In: Proc. EuroComb 2025

work page 2025
[6]

Subspace evasive sets,

Z. Dvir, and S. Lovett, “Subspace evasive sets,” in: Proceedings STOC 2012, pp. 351–358

work page 2012
[7]

Large line-free sets and their applications,

J. F ¨uhrer and V . Taranchuk, “Large line-free sets and their applications,”, arxiv 2026

work page 2026
[8]

On some batch code properties of the simplex code,

H.D.L. Hollmann, K. Khathuria, A.-E. Riet, and V . Skachek, “On some batch code properties of the simplex code,” Des. Codes Cryptogr. 91, 2023, pp. 1595–1605

work page 2023
[9]

Batch codes and their applications,

Y . Ishai, E. Kushilevitz, R. Ostrovsky, and A. Sahai, “Batch codes and their applications,” in Proc. STOC 2004, ACM Press, pp. 262–271

work page 2004
[10]

On T ´uran exponents of bipartite graphs,

T. Jiang, J. Ma, and L. Yepremyan, “On T ´uran exponents of bipartite graphs,” Combinatorics, Probability and Computing, 31(2), 2022, pp. 333–344. [ 8

work page 2022
[11]

Linear batch codes

H. Lipmaa and V . Skachek, “Linear batch codes”, in: R. Pinto, P.R. Mal- onek, and P. Vettori (Eds.), Coding Theory and Applications, pp. 245– 253, Cham, 2015, Springer Int. Publishing

work page 2015
[12]

Almost affinely disjoint subspaces,

H. Liu, N. Polianskii, I. V orobyev and A. Wachter-Zeh, “Almost affinely disjoint subspaces,” Finite Fields and Their Applications, vol. 75, pp. 101879, 2021

work page 2021
[13]

On the Minimum Length of Functional Batch Codes with Small Recovery Sets,

K. Oksner, H.D.L. Hollmann, A.-E. Riet, and V . Skachek, “On the Minimum Length of Functional Batch Codes with Small Recovery Sets,” in: Proc. WCC 2026, Paris. See also arXiv:2601.12302 [cs.IT]

work page arXiv 2026
[14]

An asymptotically optimal construction of almost affinely disjoint subspaces,

K. Otal and T. Arıkan, “An asymptotically optimal construction of almost affinely disjoint subspaces,” Finite Fields Appl. 84, 2022, 102099

work page 2022
[15]

Constructions of Batch Codes via Finite Geometry,

N. Polyanskii and I. V orobyev, “Constructions of Batch Codes via Finite Geometry,” in Proc. ISIT 2019, pp. 360–364

work page 2019
[16]

Batch Codes Through Dense Graphs Without Short Cycles,

A.S. Rawat, Z. Song, A.G. Dimakis and A. G ´al, “Batch Codes Through Dense Graphs Without Short Cycles,” IEEE Trans. Inf. Theory, vol. 62, no. 4, 2016, pp. 1592–1604

work page 2016
[17]

Batch Codes for Asyn- chronous Recovery of Data,

A.-E. Riet, V . Skachek, and E.K. Thomas, “Batch Codes for Asyn- chronous Recovery of Data,” IEEE Trans. Inf. Theory, 68 (3), 2022, pp. 1545–1559

work page 2022
[18]

Evasive Sets, Covering by Subspaces, and Point- Hyperplane Incidences,

B. Sudakov, I. Tomon, “Evasive Sets, Covering by Subspaces, and Point- Hyperplane Incidences,” Discrete Comput. Geom. 72, 2024, pp. 1333– 1347

work page 2024
[19]

Constructions and bounds for batch codes with small parameters,

E.K. Thomas and V . Skachek, “Constructions and bounds for batch codes with small parameters,” in: Proc. 5th Int. Castle Meeting Coding Theory Appl. (ICMCTA), Vihula, Estonia, 2017, pp. 283–295

work page 2017
[20]

Constructions of batch codes with near- optimal redundancy,

A. Vardy and E. Yaakobi, “Constructions of batch codes with near- optimal redundancy,” in: Proc. ISIT 2016, Barcelona, Spain, pp. 1197– 1201

work page 2016
[21]

Optimal binary switch codes with small query size,

Z. Wang, H.M. Kiah, and Y . Cassuto, “Optimal binary switch codes with small query size,” in: Proc. ISIT 2015, Hong Kong, pp. 636–640

work page 2015
[22]

Codes for network switches,

Z. Wang, O. Shaked, Y . Cassuto, and J. Bruck, “Codes for network switches,” in: Proc. ISIT 2013, Istanbul, Turkey, pp. 1057–1061

work page 2013
[23]

Bounds for batch codes with restricted query size,

H. Zhang and V . Skachek, “Bounds for batch codes with restricted query size,” in: Proc. ISIT 2016, Barcelona, Spain, pp. 1192–1196

work page 2016