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