Metraipolis › archive › dc_1f1920ec556d

Optimal Codes for the Coverage Depth Problem and the Performance of Random Codes — arXiv:2610.07370

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.07370
License (as archived)
CC0-1.0
Archived
2026-10-07T12:10:16.468Z
SHA-256 of the archived text
1a1684bfb4e0a6984580ce8ecd28ee4e338a3a5fb09ac3af5f05b47b61a838f1
Stable URL of this page
https://metraipolis.com/documento/dc_1f1920ec556d

How to cite

Optimal Codes for the Coverage Depth Problem and the Performance of Random Codes — arXiv:2610.07370 — arXiv (en), https://arxiv.org/abs/2610.07370 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_1f1920ec556d (Metraipolis archive dc_1f1920ec556d, sha256 1a1684bfb4e0a6984580ce8ecd28ee4e338a3a5fb09ac3af5f05b47b61a838f1)
BibTeX
@misc{dc1f1920ec556d,
  title = {Optimal Codes for the Coverage Depth Problem and the Performance of Random Codes — arXiv:2610.07370},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.07370},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_1f1920ec556d; sha256 1a1684bfb4e0a6984580ce8ecd28ee4e338a3a5fb09ac3af5f05b47b61a838f1},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.07370. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.IT, nuovi lavori del giorno).
Categorie arXiv: Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2610.07370 — 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-07T11:42:17.254Z dalla pagina https://arxiv.org/list/math.IT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).