A mathematical preprint identifies a trade-off in random access to information represented by linear codes. In the paper’s displayed dimension-three comparisons, balanced quasi-arcs have the lowest expected recovery times when the request is for one or two symbols, while the systematic MDS benchmark is lowest when the request is for all symbols.
The objects under study are generator matrices of linear codes and their columns. The paper compares three named encoder families—systematic MDS encoders, simplex encoders and balanced quasi-arcs—as different column geometries. The supplied document is arXiv preprint arXiv:2608.20152v1, dated 20 August 2026.
A model of selective recovery
At the centre is a question between two endpoints. For a nonempty requested set of information symbols, how many random column samples are needed before all the requested information vectors can be recovered? Requesting one symbol is singleton recovery; requesting all k symbols is full recovery. The framework connects those endpoints by allowing every intermediate requested-set size.
The sampling rule is specific: columns are sampled independently, uniformly and with replacement. That means a column may appear again in the sequence of draws. For each requested set, the authors count how many subsets of s columns can recover it. Those counts, denoted α_I(s), feed an exact formula involving harmonic numbers for the expected recovery time.
From that identity, the paper compares average expected recovery time across requested sets of a fixed size with the worst case. Its general order-statistics result places the worst-case value at or above the average and gives a lower bound for the average based on the order in which singleton requests are recovered.
For systematic encoders, the analysis also gives an upper bound of nH_m for the maximal expected recovery time when m symbols are requested. The notation combines the code length n with the harmonic number H_m. It is a bound on the worst expected wait, not a claim that every encoder reaches it.
What systematic MDS changes
The systematic MDS family produces the clearest uniform result. Its expected recovery time depends only on m, the number of requested symbols: every requested set of that size has the same value. The maximum and average therefore coincide for that size.
That value increases strictly with m before full recovery. For fixed k and m, it converges to k as n grows. At the full-recovery endpoint, the systematic-MDS value matches the universal lower bound, making it optimal for full recovery within the model used here.
Different geometries, different winners
Simplex encoders offer a different exact treatment. The paper derives finite-geometric formulas for them, and symmetry makes their maximum and average expected recovery times coincide for requested sets with the same cardinality.
In the dimension-three examples, the binary simplex encoder has expected values of 3, 11/3 and 47/12 for one-, two- and three-symbol recovery. The corresponding ternary values are 3, 41/12 and 127/36.
The examples make the central point visible: expected recovery time changes with the size of the requested set, so a code cannot be judged by a single recovery figure when partial and full access are separate goals.
Balanced quasi-arcs in dimension three provide a third pattern. As the balanced quasi-arc weight x tends to infinity, the reported expectations approach 17/6 for one-symbol recovery, 3 for two-symbol recovery and 19/6 for full recovery.
Length-matched comparisons in the same dimension point in opposite directions at different request sizes. Balanced quasi-arcs are lowest for singleton and two-symbol recovery in the displayed rows; the MDS benchmark is lowest for full recovery.
The authors interpret the split as a local-versus-global trade-off: the geometry that helps with partial recovery need not be the geometry that performs best at the all-symbol endpoint.
The boundaries of the result
These are mathematical results under a fixed sampling model. The analysis is built from exact identities, inequalities, finite-geometric counts and selected numerical comparisons. It therefore addresses code geometry under stated assumptions, rather than reporting a measured retrieval trial.
The comparison’s scope is correspondingly narrow. It identifies the lowest values in displayed length-matched comparisons in dimension three; it does not extend that ranking to every field, length or higher dimension.
The MDS conclusion is also conditional on the stated model: it says the systematic-MDS value is optimal at full recovery within that model, not that a matching systematic MDS encoder exists for every parameter set.
The conclusions are tied to independent, uniform sampling with replacement. Questions involving a different sampling distribution or additional storage constraints fall outside the calculation described here.
A result still at the preprint stage
The acknowledgments disclose overlapping systematic-MDS results with a recent preprint. They also state that this work was obtained independently and had been included in a 2025 master’s thesis before the authors learned of that preprint.
The work received Villum Fonden grant VIL52303. The acknowledgments also say that the third author received DTU hospitality during August 2025 and partial support from GNSAGA-INdAM.
For selective retrieval, the message is conditional: the best encoder geometry may depend on whether the task is recovering a few requested symbols or the full information set. The preprint supplies exact formulas and comparisons for that choice, while keeping the conclusions within its stated sampling model.
Paper data and sources
Original title: The Generalized Random Access Problem for Linear Codes
Authors: Anina Gruica, Antonio Petrillo, Ferdinando Zullo
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text