List Size of Random Linear Codes: Optimality and the Limits of Average-Radius List Decoding
Abstract
Guruswami, Li, Mosheiff, Resch, Silas and Wootters conjectured that, for every fixed prime power q and p∈(0,1−1/q), random linear codes of rate 1−hq(p)−ε have list size hq(p)/ε·(1+o(1)) as ε→0, both for list decoding and average-radius list decoding. The conjecture was known for q=2 and remained open for larger alphabets. We prove the conjecture for list decoding for every prime power q, with the sharper bound L=hq(p)/ε+Op,q(1). In contrast, we disprove the conjecture for average-radius list decoding. We show that the required list-size leading constant is at least p(1+logq((q−1)(1−p))/p), which is strictly larger than hq(p) whenever qp(1−p)>1. Moreover, for p=1−λ/q with fixed λ>1, the required leading constant can be as large as (logλ/eλ+oq(1))q/(log q).
Related
- Average-Radius List-Decodability of Random Linear Codes
- Limits of Weight-Bounded Redundant Checks for Peeling Decoding of Random Regular LDPC Codes
- A rate for the average vacancy of uniformly random matchings in linear hypergraphs
- A $π/ 4$ lower bound for random access in symmetric linear ensembles under optimal decoding
- Achieving an O(1/N) Optimality Gap in Average-Reward Weakly-Coupled MDPs
BibTeX
@misc{yuan2026list,
title = {{List Size of Random Linear Codes: Optimality and the Limits of Average-Radius List Decoding}},
author = {Chen Yuan and Ruiqi Zhu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.01070},
eprint = {2609.01070},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.01070},
}
RIS
TY - UNPB
TI - List Size of Random Linear Codes: Optimality and the Limits of Average-Radius List Decoding
AU - Chen Yuan
AU - Ruiqi Zhu
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2609.01070
UR - https://arxiv.org/abs/2609.01070
AB - Guruswami, Li, Mosheiff, Resch, Silas and Wootters conjectured that, for every fixed prime power q and p∈(0,1−1/q), random linear codes of rate 1−h_q(p)−ε have list size h_q(p)/ε·(1+o(1)) as ε→0, both for list decoding and average-radius list decoding. The conjecture was known for q=2 and remained open for larger alphabets. We prove the conjecture for list decoding for every prime power q, with the sharper bound L=h_q(p)/ε+O_p,q(1). In contrast, we disprove the conjecture for average-radius list decoding. We show that the required list-size leading constant is at least p(1+log_q((q−1)(1−p))/p), which is strictly larger than h_q(p) whenever q^p(1−p)>1. Moreover, for p=1−λ/q with fixed λ>1, the required leading constant can be as large as (logλ/eλ+o_q(1))q/(log q).
ER -