Polynomial-Time Constructions of Asymptotically Good Random Access Codes from Linear Codes
Abstract
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≥2, together with an encoder based on its orthogonal-array property, yields an (n,n−k)q-RAC with worst-case decoding success probability pwc=1/q+(1−1/q)(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 RRAC=(n−k)/n∈(0,1). Numerical results demonstrate favorable finite-length performance of both constructions.
Related
- Sparse Polynomial GCD Algorithms Asymptotically Linear in All Fundamental Parameters
- A Matroidal Framework for Random Access in Linear Codes
- A $π/ 4$ lower bound for random access in symmetric linear ensembles under optimal decoding
- Explicit and asymptotically good constructions of Algebraic Geometry codes in the sum-rank metric
- Random Tournaments Are Asymptotically Almost Surely Link-irregular
BibTeX
@misc{kondo2026polynomialtime,
title = {{Polynomial-Time Constructions of Asymptotically Good Random Access Codes from Linear Codes}},
author = {Ruho Kondo and Yota Maeda},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.38429},
eprint = {2610.38429},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.38429},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Polynomial-Time Constructions of Asymptotically Good Random Access Codes from Linear Codes
AU - Ruho Kondo
AU - Yota Maeda
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2610.38429
UR - https://arxiv.org/abs/2610.38429
AB - 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≥2, together with an encoder based on its orthogonal-array property, yields an (n,n−k)_q-RAC with worst-case decoding success probability p_wc=1/q+(1−1/q)(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_RAC=(n−k)/n∈(0,1). Numerical results demonstrate favorable finite-length performance of both constructions.
ER -