CS Paper Radar

The Generalized Random Access Problem for Linear Codes

Anina Gruica, Antonio Petrillo, Ferdinando Zullo

cs.IT math.CO ·submitted 2026-08-20 15:11 UTC · v1
hot direction

Abstract

Random access is a central requirement in DNA-based storage systems: one would like to recover selected information symbols without sequencing the whole encoded object. A recent combinatorial model associates to a generator matrix $G\in F_q^{k\times n}$ the random variable $τ_i(G)$, measuring the number of sampled columns needed to recover the information vector $e_i$. We study the cardinality-based extremal and finite-geometric aspects of simultaneous multi-symbol recovery. For a nonempty set $I\subseteq[k]$, let $τ_I(G)$ denote the number of random column samples needed until all vectors $e_i$, $i\in I$, lie in the span of the observed columns. This variable interpolates between the singleton random access problem and the full-recovery problem underlying coverage depth. For each $m$, we introduce uniform worst-case and average parameters over all requested sets $I$ with $|I|=m$. Using the known subset-counting formula for $E[τ_I(G)]$, we establish general upper and lower bounds for these parameters. In particular, the lower bounds are expressed through order statistics of the singleton recovery variables and specialize to the known singleton bounds when $m=1$. For systematic MDS encoders, we record an equivalent form of the known multi-symbol expectation formula and derive monotonicity and asymptotic consequences. For simplex encoders in arbitrary dimension, we obtain closed formulae in terms of Gaussian binomial coefficients; the full-recovery endpoint agrees with the known coverage-depth formula for simplex codes. Finally, in dimension three we study balanced quasi-arcs and compare their values with the simplex and MDS benchmarks.

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Codes for the Coverage Depth Problem and the Performance of Random Codes

cs.IT ·2026-10-05 ·Roee Gross, Yitzchak Grunbaum, Matteo Bertuzzo, Eitan Yaakobi, Alberto Ravagnani
benchmarkhot direction similarity 0.75
Abstract

DNA storage systems retrieve information by randomly sampling synthesized DNA strands, making the number of reads required for successful recovery a fundamental performance measure. This motivates the coverage depth problem: for given code parameters, determine a linear code that minimizes the expected number of randomly sampled columns required to span the entire information space. While MDS codes are known to be optimal whenever they exist, identifying optimal codes in parameter regimes where MDS codes do not exist remains largely open. In this work, we derive a general formula for the expectation in the coverage depth setting, and apply this result to establish the optimality of the $q$-ary simplex code for the parameters that allow its existence. Moreover, we show the optimality of the $q$-ary Hamming code by relating coverage depth to independent sets in the dual code and exploiting log-concavity properties of matroid basis-generating polynomials. We further analyze random linear codes, derive an exact expression for their expected coverage depth, and show that, in the constant-rate regime, their additive gap from the MDS benchmark remains bounded independently of the code length.

0.44

A $π/ 4$ lower bound for random access in symmetric linear ensembles under optimal decoding

cs.IT ·2026-10-28 ·Daniella Bar-Lev, Ohad Elishco, Ryan Gabrys
theory similarity 0.71
Abstract

We study the expected number of random linear observations required to recover a prescribed information symbol. For ensembles with uniformly random supports, independently sampled nonzero coefficients, and uniformly bounded column weights, we prove that the asymptotic normalized expected recovery time is at least $π/4$ under optimal decoding. The result holds over finite or infinite fields and extends the lower bound previously established for binary fully symmetric codes under peeling decoding. For singleton - pair observations, we determine the exact limiting expectation and show that optimal and peeling decoding have the same limit, independently of the field and coefficient distribution. The minimum within this family is approximately $0.793933445$, which explicit constructions attain asymptotically over every fixed finite field.

0.47

A Hyperbolic Bound for File Retrieval in DNA-Based Data Storage

cs.IT math.CO ·2026-09-28 ·Constantinos Vasilios Argyris Vlachos, Daniella Bar-Lev
theory similarity 0.70
Abstract

In DNA-based storage systems, data are retrieved by sequencing molecules sampled from a DNA pool. We study how the way coding redundancy is shared between files affects their expected retrieval times. Our focus lies on the case of two files that are encoded by a systematic linear code over an arbitrary finite field. We consider the conjecture that the sum obtained by dividing each file dimension by its expected retrieval time is at most one whenever the dimension of at least one file is more than one. For this, we develop a geometric view of the retrieval process. As molecules are sampled, we follow the growing span of the corresponding columns of the generator matrix and track how much of this span comes from each file. Among the samples that enlarge the overall span, this lets us compare those that make progress toward recovering both files with those that make progress toward neither. We call a column mixed if the corresponding encoded symbol combines information from both files. In this work, we sharpen a projection bound and use it to control the effect of mixed columns. We prove the conjecture whenever the total information dimension is at least twice the number of mixed columns plus two. For equal-sized files, this allows up to one fewer mixed column than the dimension of either file and extends the previous result for codes with no mixed columns.

0.40

A Matroidal Framework for Random Access in Linear Codes

cs.IT math.CO ·2026-10-20 ·Daniella Bar-Lev, Hiram H. López, Gretchen L. Matthews, Flavio Salizzoni
similarity 0.69
Abstract · 6 pages

We study random access in linear codes when codeword symbols are sampled independently and uniformly with replacement. A code is recovery balanced if the expected number of samples required to recover a codeword coordinate is the same for every coordinate. We express the recovery expectations in terms of the associated matroid and derive a coordinatewise identity relating these values for a code and its dual. This proves that a linear code is recovery balanced if and only if its dual is recovery balanced, establishing a conjecture of Gruica et al. We further define the recovery balance for arbitrary matroids and show that asymptotically almost every sparse paving matroid is not recovery balanced.

0.35

The Coverage Depth Problem in Distributed DNA Data Storage

cs.IT math.CO ·2026-10-02 ·Xiangliang Kong, Ohad Elishco, Chen Wang, Tolga M. Duman
theoryhighly cited similarity 0.69
Abstract · 33 pages, 2 figures

Random sampling in DNA sequencing produces repeated reads, increasing retrieval latency and sequencing cost. We study the coverage-depth problem for full-message recovery in distributed DNA storage under noiseless uniform sampling, where strands are partitioned among $M$ containers and one strand is independently sampled with replacement from each container per round. For arbitrary linear codes and ordered partitions, we derive exact formulas for the recovery-time distribution and expectation. We prove that MDS codes, whenever they exist, are optimal for every fixed partition, and establish a universal lower bound on the expected total read cost together with its equality conditions. For MDS codes, we identify container-size regimes that yield genuine savings in total reads and regimes that provide only parallelism without changing the asymptotic sequencing cost. For simplex codes, we prove that the $q$-ary simplex code is, up to isomorphism, the unique single-container minimizer among codes with the same parameters, resolving a recent conjecture by Bertuzzo, Ravagnani, and Yaakobi. We further construct a partition attaining the minimum total read cost and derive bounds for intermediate and balanced partitions. These results clarify when distributed sampling reduces latency alone and when it also reduces sequencing cost.

0.49

Polynomial-Time Constructions of Asymptotically Good Random Access Codes from Linear Codes

cs.IT ·2026-10-28 ·Ruho Kondo, Yota Maeda
similarity 0.66
Abstract · 13 pages, 5 figures,

Random access codes (RACs) encode a $q$-ary input string into fewer $q$-ary symbols while allowing any requested input symbol to be recovered with probability above the random-guessing value $1/q$. However, it remains unclear what asymptotic guarantees on compression and recovery probability should be required of RACs. We address this question by introducing the notion of asymptotically good RACs and give two polynomial-time constructions. First, an $[n,k,d]_q$ linear code with $d\ge2$, together with an encoder based on its orthogonal-array property, yields an $(n,n-k)_q$-RAC with worst-case decoding success probability \[ p_{\rm wc}=\frac{1}{q}+\left(1-\frac{1}{q}\right)\frac{d-2}{n}. \] These OA-RACs are asymptotically good whenever the underlying linear codes are, and Garcia--Stichtenoth algebraic-geometry codes give a concrete polynomial-time realization. Second, a direct-sum strategy using OA-RACs derived from $q$-ary Hamming codes and the trivial $(1,1)_q$-RAC yields asymptotically good RAC families at every prescribed RAC rate $R_{\rm RAC}=(n-k)/n\in(0,1)$. Numerical results demonstrate favorable finite-length performance of both constructions.

0.23

Thresholds for Local Coordinate-Wise Linear Properties of Random One-Point AG Codes

cs.IT ·2026-10-08 ·Chen Yuan, Ruiqi Zhu
theory similarity 0.66
Abstract · 37 pages

Local coordinate-wise linear (LCL) properties provide a unified framework for studying list decoding, list recovery and other local properties of linear codes. We prove that random one-point algebraic geometry (AG) codes have the same LCL threshold rates as random linear codes under explicit alphabet and sampling conditions. More precisely, for a family of local profiles with random linear code threshold $R_{\mathcal P}$, a random one-point AG code avoids all such profiles below $R_{\mathcal P}-\varepsilon$ and contains one above $R_{\mathcal P}+\varepsilon$, with explicit failure bounds on both sides. Our proof also removes an auxiliary lower bound on the number of available rational places that arises in a direct adaptation of the Reed--Solomon argument and requires no additional genus-dependent rate gap. We also observe that the previously claimed above threshold proof for random Reed--Solomon codes does not establish the required probability lower bound. The containment relation used in that argument gives the probability comparison in the opposite direction from what is needed. We give a different above threshold argument, which in particular also yields an alternative proof in the genus zero case. Combining our threshold theorem with recent results for random linear codes gives a collection of new list decoding, average weight list decoding and list recovery guarantees for random one-point AG codes. We further obtain new correlated agreement and proximity gap results for polynomial curves. These results extend the LCL threshold framework from random linear and Reed--Solomon codes to random one-point AG codes.

0.18

Bounds on the Service Rates of Linear Codes and their Connections to Combinatorial Designs

cs.IT ·2026-10-19 ·Monika Yadav, Priyanka Choudhary, Maheshanand Bhaintwal
theory similarity 0.65
Abstract

The service rate region of a distributed storage system describes the set of concurrent demand vectors that can be served without overloading any individual server, and is a fundamental measure of how effectively redundancy is used. In this paper, we investigate aggregate service rates in distributed data storage systems based on linear codes over arbitrary finite fields. We first derive an upper bound on the aggregate service rate for an arbitrary subset of $t$ data objects in terms of the dual distance and the sizes of their smallest recovery sets. For systematic generator matrices, this bound simplifies to an expression depending only on the code length, the dual distance, and the cardinality of the selected subset. This result extends existing bounds and provides a subset-wise formulation of the First Dual Distance Bound. We then establish conditions under which this upper bound is attained. We apply our results to several important families of linear codes, including MDS codes, Reed-Muller codes, constacyclic codes, and extended Golay codes, and obtain exact values of the maximum aggregate service rates for the corresponding subsets of data objects.

0.25