Low-density parity-check codes achieve list-decoding capacity

DOI10.1137/20M1365934MaRDI QIDQ5020732zbMATH OpenOpenAlexFDO

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

Publication date 7 January 2022

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.06430

zbMATH Keywords

Gallagher codesLDPC codeslist-decodinglocal propertiesrandom linear codesthreshold

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Decoding (94B35)

Abstract: 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 $extitlocal$ 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-decodability, list-recoverability and average-radius list-decodability. 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 $mathcalP$, there is some $R^{\ast }$ so that random linear codes of rate slightly less than $R^{\ast }$ satisfy $mathcalP$ 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 }$.

Recommendations

• On the list-decodability of random linear codes
• On the list decodability of random linear codes with large error rates
• The capacity of low-density parity-check codes under message-passing decoding
• On the error-correcting capability of LDPC codes
• LP decoding achieves capacity

Cites work

• A recursive approach to low complexity codes
• Analysis of Boolean Functions
• Average-radius list-recoverability of random linear codes
• Combinatorial bounds for list decoding
• Every list-decodable code for high noise has abundant near-optimal rate puncturings
• Expander codes
• Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy
• Explicit subspace designs
• Folded codes from function field towers and improved optimal rate list decoding
• Graphical models, exponential families, and variational inference
• scientific article; zbMATH DE number 3174791 (Why is no real title available?)
• scientific article; zbMATH DE number 3760081 (Why is no real title available?)
• scientific article; zbMATH DE number 1306883 (Why is no real title available?)
• scientific article; zbMATH DE number 607286 (Why is no real title available?)
• scientific article; zbMATH DE number 7758311 (Why is no real title available?)
• Improved list-decodability of random linear binary codes
• Information Theory and Statistics: A Tutorial
• Iterative Decoding of Low-Density Parity Check Codes (A Survey)
• Linear-Algebraic List Decoding for Variants of Reed–Solomon Codes
• List decoding from erasures: bounds and code constructions
• List decoding Reed-Solomon, algebraic-geometric, and Gabidulin subcodes up to the Singleton bound
• List decoding with double samplers
• List-decoding multiplicity codes
• Local list recovery of high-rate tensor codes and applications
• On expander codes
• On List Recovery of High-Rate Tensor Codes
• On the list decodability of random linear codes with large error rates
• On the List-Decodability of Random Linear Codes
• On the weight distribution of random binary linear codes
• Random graphs.
• Restricted isometry of Fourier matrices and list decodability of random linear codes
• Spatially Coupled Ensembles Universally Achieve Capacity Under Belief Propagation
• Subspace evasive sets
• Thresholds in the lattice of subspaces of \(\mathbb{F}_q^n\)
• Thresholds versus fractional expectation-thresholds

Cited in

(1)

• scientific article; zbMATH DE number 4216926 (Why is no real title available?)

This page was built for publication: Low-density parity-check codes achieve list-decoding capacity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5020732)