Metraipolis › archive › dc_cf25369f883d
Polynomial-Time Constructions of Asymptotically Good Random Access Codes from Linear Codes — arXiv:2610.38429
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.38429
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-01T02:39:39.697Z
- SHA-256 of the archived text
16cbdd7115807a2cc57cfed42602f9a3682ff2700c653249580bf9db2b3d702f- Stable URL of this page
https://metraipolis.com/documento/dc_cf25369f883d
How to cite
Polynomial-Time Constructions of Asymptotically Good Random Access Codes from Linear Codes — arXiv:2610.38429 — arXiv (en), https://arxiv.org/abs/2610.38429 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cf25369f883d (Metraipolis archive dc_cf25369f883d, sha256 16cbdd7115807a2cc57cfed42602f9a3682ff2700c653249580bf9db2b3d702f)
BibTeX
@misc{dccf25369f883d,
title = {Polynomial-Time Constructions of Asymptotically Good Random Access Codes from Linear Codes — arXiv:2610.38429},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.38429},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cf25369f883d; sha256 16cbdd7115807a2cc57cfed42602f9a3682ff2700c653249580bf9db2b3d702f},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.38429. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
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.38429 — 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-11-01T02:15:43.720Z dalla pagina https://arxiv.org/list/math.IT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).