The list size of random linear and LDPC codes at capacity
Abstract
We show that for every prime power q and ρ∈(0,1−1/q) there exists ε0(q, ρ) > 0 such that for all positive ε < ε0(q, ρ), a random linear code over 𝔽q of rate 1−hq(ρ)−ε has list size ⌊ hq(ρ)/ε⌋ or ⌊ hq(ρ)/ε⌋+1 with probability 1−o(1). Before this work, the list size was known only up to a constant factor for q≥3, and for q=2 it was known to be either ⌊ h2(ρ)/ε⌋−1, ⌊ h2(ρ)/ε⌋ or ⌊ h2(ρ)/ε⌋+1. We also show that the same two-point concentration holds for the list size of random LDPC codes. This follows from a general theorem establishing that random LDPC codes and random linear codes have the same threshold rate for distance, list decoding, list recovery from errors and any other \emph{convex} property, which answers a question of Mosheiff, Resch, Ron-Zewi, Silas and Wootters.
Related
- List Size of Random Linear Codes: Optimality and the Limits of Average-Radius List Decoding
- Average-Radius List-Decodability of Random Linear Codes
- Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time
- Algorithmic List Decoding of Reed-Solomon Codes up to Capacity
- Reed-Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps
BibTeX
@misc{silas2026list,
title = {{The list size of random linear and LDPC codes at capacity}},
author = {Shashwat Silas},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.06570},
eprint = {2609.06570},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.06570},
}
RIS
TY - UNPB
TI - The list size of random linear and LDPC codes at capacity
AU - Shashwat Silas
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2609.06570
UR - https://arxiv.org/abs/2609.06570
AB - We show that for every prime power q and ρ∈(0,1−1/q) there exists ε_0(q, ρ) > 0 such that for all positive ε < ε_0(q, ρ), a random linear code over 𝔽_q of rate 1−h_q(ρ)−ε has list size ⌊ h_q(ρ)/ε⌋ or ⌊ h_q(ρ)/ε⌋+1 with probability 1−o(1). Before this work, the list size was known only up to a constant factor for q≥3, and for q=2 it was known to be either ⌊ h_2(ρ)/ε⌋−1, ⌊ h_2(ρ)/ε⌋ or ⌊ h_2(ρ)/ε⌋+1. We also show that the same two-point concentration holds for the list size of random LDPC codes. This follows from a general theorem establishing that random LDPC codes and random linear codes have the same threshold rate for distance, list decoding, list recovery from errors and any other \emph{convex} property, which answers a question of Mosheiff, Resch, Ron-Zewi, Silas and Wootters.
ER -