Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy

DOI10.1109/TIT.2007.911222zbMATHOpenAlexMaRDI QIDQ3604484FDO

Authors Atri Rudra, Venkatesan Guruswami

Publication date 24 February 2009

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

zbMATH Keywords

error-correcting codesfolded Reed-Solomon codes

Mathematics Subject Classification ID

Coding theorems (Shannon theory) (94A24) Decoding (94B35)

Abstract: We present error-correcting codes that achieve the information-theoretically best possible trade-off between the rate and error-correction radius. Specifically, for every $0<R<1$ and $eps>0$, we present an explicit construction of error-correcting codes of rate $R$ that can be list decoded in polynomial time up to a fraction $(1-R-eps)$ of {em worst-case} errors. At least theoretically, this meets one of the central challenges in algorithmic coding theory. Our codes are simple to describe: they are {em folded Reed-Solomon codes}, which are in fact {em exactly} Reed-Solomon (RS) codes, but viewed as a code over a larger alphabet by careful bundling of codeword symbols. Given the ubiquity of RS codes, this is an appealing feature of our result, and in fact our methods directly yield better decoding algorithms for RS codes when errors occur in {em phased bursts}. The alphabet size of these folded RS codes is polynomial in the block length. We are able to reduce this to a constant (depending on $eps$) using ideas concerning ``list recovery and expander-based codes from cite{GI-focs01,GI-ieeejl}. Concatenating the folded RS codes with suitable inner codes also gives us polynomial time constructible binary codes that can be efficiently list decoded up to the Zyablov bound, i.e., up to twice the radius achieved by the standard GMD decoding of concatenated codes.

Recommendations

• Explicit capacity-achieving list-decodable codes
• Two theorems on list decoding (extended abstract)
• List decoding of error-correcting codes. Winning thesis of the 2002 ACM Doctoral Dissertation Competition
• Improved decoding of Reed-Solomon and algebraic-geometry codes
• List Decoding of Binary Codes–A Brief Survey of Some Recent Results

Cited in

(36)

• Lossless dimension expanders via linearized polynomials and subspace designs
• Optimal rate algebraic list decoding using narrow ray class fields
• Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes
• List Decoding of Binary Codes–A Brief Survey of Some Recent Results
• Reduced lists of error patterns for maximum likelihood soft decoding
• A novel elementary construction of matching vectors
• Explicit subspace designs
• Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding
• Parallel Hashing via List Recoverability
• Nearly optimal robust secret sharing
• Nearly optimal pseudorandomness from hardness
• Revisiting approximate polynomial common divisor problem and noisy multipolynomial reconstruction
• Generalized Singleton Bound and List-Decoding Reed–Solomon Codes Beyond the Johnson Radius
• scientific article; zbMATH DE number 7250144 (Why is no real title available?)
• Bridging Shannon and Hamming: list error-correction with optimal rate
• On the error-correcting radius of folded Reed-Solomon code designs
• Variety evasive sets
• Computing minimal interpolation bases
• Rank-metric codes and their applications
• List-Decoding with Double Samplers
• NP-hardness of Reed-Solomon decoding, and the Prouhet-Tarry-Escott problem
• Privacy-preserving support vector machines with flexible deployment and error correction
• Low-density parity-check codes achieve list-decoding capacity
• Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes
• Synchronization strings: list decoding for insertions and deletions
• Cyclotomic function fields, Artin-Frobenius automorphisms, and list error correction with optimal rate
• Optimal Rate List Decoding via Derivative Codes
• High-rate codes with sublinear-time decoding
• Explicit capacity-achieving list-decodable codes
• Group homomorphisms as error correcting codes
• Local list recovery of high-rate tensor codes and applications
• Improved list-decodability of random linear binary codes
• Interpolation-based decoding of folded variants of linearized and skew Reed-Solomon codes
• Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings
• Algebraic decoding of folded Gabidulin codes
• scientific article; zbMATH DE number 7650135 (Why is no real title available?)

This page was built for publication: Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy

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