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

DOI10.1109/TIT.2007.911222MaRDI QIDQ3604484zbMATH OpenOpenAlexFDO

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)

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

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)