Metraipolis › archive › dc_95441e6f0897
The Generalized Random Access Problem for Linear Codes — arXiv:2608.20152
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.20152
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-18T12:00:44.686Z
- SHA-256 of the archived text
9344294b6efc06d63f65e00b697031151d332cd83cd88b65b8bf8da578020445- Stable URL of this page
https://metraipolis.com/documento/dc_95441e6f0897
How to cite
The Generalized Random Access Problem for Linear Codes — arXiv:2608.20152 — arXiv (en), https://arxiv.org/abs/2608.20152 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_95441e6f0897 (Metraipolis archive dc_95441e6f0897, sha256 9344294b6efc06d63f65e00b697031151d332cd83cd88b65b8bf8da578020445)
BibTeX
@misc{dc95441e6f0897,
title = {The Generalized Random Access Problem for Linear Codes — arXiv:2608.20152},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.20152},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_95441e6f0897; sha256 9344294b6efc06d63f65e00b697031151d332cd83cd88b65b8bf8da578020445},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.20152. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\tau_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 $\tau_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[\tau_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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-21 in math.IT).
Categorie arXiv: Information Theory (cs.IT) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.20152 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T11:58:25.127Z dalla pagina https://arxiv.org/catchup/math.IT/2026-08-21?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).