PreprintCC BY 4.0arXiv
Average-Radius List-Decodability of Random Linear Codes
Abstract
We prove that for every prime power q and every p ∈ (0, 1−1/q), a random 𝔽q-linear code of rate 1 − hq(p) − ε is (p, Cp,q/ε)-average-radius list-decodable with probability at least 1 − q−Ω(n), i.e., for every center y ∈ 𝔽qn, the Cp,q/ε codewords closest to y have average fractional Hamming distance at least p from y. This extends a similar result for (standard) list-decoding due to Guruswami, Håstad, and Kopparty (2010) to the stronger average-radius guarantee, with the same O(1/ε) list size. For average-radius list-decoding, such a result was previously known only for binary linear codes (Guruswami, Li, Mosheiff, Resch, Silas, and Wootters, 2021) and for general (non-linear) random codes over arbitrary alphabets (Elias, 1991).
Related
- List Size of Random Linear Codes: Optimality and the Limits of Average-Radius List Decoding
- Optimal Average Success Probabilities of Binary (n,n−1) and (n,n−2) Quantum Random Access Codes
- A rate for the average vacancy of uniformly random matchings in linear hypergraphs
- A Matroidal Framework for Random Access in Linear Codes
- Polynomial-Time Constructions of Asymptotically Good Random Access Codes from Linear Codes
BibTeX
@misc{guruswami2026averageradius,
title = {{Average-Radius List-Decodability of Random Linear Codes}},
author = {Venkatesan Guruswami and Shilun Li and Mihir Singhal},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.22663},
eprint = {2608.22663},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.22663},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Average-Radius List-Decodability of Random Linear Codes
AU - Venkatesan Guruswami
AU - Shilun Li
AU - Mihir Singhal
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2608.22663
UR - https://arxiv.org/abs/2608.22663
AB - We prove that for every prime power q and every p ∈ (0, 1−1/q), a random 𝔽_q-linear code of rate 1 − h_q(p) − ε is (p, C_p,q/ε)-average-radius list-decodable with probability at least 1 − q^−Ω(n), i.e., for every center y ∈ 𝔽_q^n, the C_p,q/ε codewords closest to y have average fractional Hamming distance at least p from y. This extends a similar result for (standard) list-decoding due to Guruswami, Håstad, and Kopparty (2010) to the stronger average-radius guarantee, with the same O(1/ε) list size. For average-radius list-decoding, such a result was previously known only for binary linear codes (Guruswami, Li, Mosheiff, Resch, Silas, and Wootters, 2021) and for general (non-linear) random codes over arbitrary alphabets (Elias, 1991).
ER -