LDPC Codes Achieve List Decoding Capacity

We show that Gallager's ensemble of Low-Density Parity Check (LDPC) codes achieves list-decoding capacity with high probability. These are the first graph-based codes shown to have this property. This result opens up a potential avenue towards truly linear-time list-decodable codes that achieve list-decoding capacity. Our result on list decoding follows from a much more general result: any local property satisfied with high probability by a random linear code is also satisfied with high probability by a random LDPC code from Gallager's distribution. Local properties are properties characterized by the exclusion of small sets of codewords, and include list-decoding, list-recovery and average-radius list-decoding. In order to prove our results on LDPC codes, we establish sharp thresholds for when local properties are satisfied by a random linear code. More precisely, we show that for any local property $\mathcal{P}$, there is some $R^{\ast}$ so that random linear codes of rate slightly less than $R^{\ast}$ satisfy $\mathcal{P}$ with high probability, while random linear codes of rate slightly more than $R^{\ast}$ with high probability do not. We also give a characterization of the threshold rate $R^{\ast}$. This is an extended abstract. The full version is available at https: //arxiv. org/abs/1909. 06430

Authors

• Jonathan Mosheiff
• Nicolas Resch
• Noga Ron-Zewi
• Shashwat Silas
• Mary Wootters

Keywords

• Parity check codes
• Linear codes
• Decoding
• Computer science
• Capacity planning
• Bipartite graph
• Task analysis
• Low-density Parity-check Codes
• Low-density Parity-check
• List-decoding Capacity
• High Probability
• Local Properties
• Codeword
• Random Code
• Linear Code
• Parity-check
• Building Blocks
• Efficient Algorithm
• Line Of Work
• Fourier Analysis
• Random Matrix
• Binary Code
• Random Graph
• Almost Surely
• Finite Field
• Coding Theory
• Linear-time Algorithm
• Smooth Distribution
• Reed-Solomon Codes
• Code Size
• List Size
• General Theorem
• Parity-check Matrix
• Alphabet Size
• LDPC
• List Decoding
• Local Property
• Thershold