Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy
From MaRDI portal
Publication:3604484
DOI10.1109/TIT.2007.911222zbMATH Open1205.94125arXivcs/0511072OpenAlexW2146078064MaRDI QIDQ3604484FDOQ3604484
Authors: Atri Rudra, Venkatesan Guruswami 
Publication date: 24 February 2009
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
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 and , we present an explicit construction of error-correcting codes of rate that can be list decoded in polynomial time up to a fraction 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 ) 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.
Full work available at URL: https://arxiv.org/abs/cs/0511072
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)
- Variety evasive sets
- Parallel Hashing via List Recoverability
- List-Decoding with Double Samplers
- Lossless dimension expanders via linearized polynomials and subspace designs
- Low-density parity-check codes achieve list-decoding capacity
- A novel elementary construction of matching vectors
- 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
- Generalized Singleton Bound and List-Decoding Reed–Solomon Codes Beyond the Johnson Radius
- Computing minimal interpolation bases
- Title not available (Why is that?)
- Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes
- Optimal rate algebraic list decoding using narrow ray class fields
- Title not available (Why is that?)
- Reduced lists of error patterns for maximum likelihood soft decoding
- Cyclotomic function fields, Artin-Frobenius automorphisms, and list error correction with optimal rate
- Improved list-decodability of random linear binary codes
- Explicit subspace designs
- Nearly optimal robust secret sharing
- Revisiting approximate polynomial common divisor problem and noisy multipolynomial reconstruction
- Rank-metric codes and their applications
- NP-hardness of Reed-Solomon decoding, and the Prouhet-Tarry-Escott problem
- Group homomorphisms as error correcting codes
- 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
- 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
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)
