Decoding of Reed Solomon codes beyond the error-correction bound

DOI10.1006/jcom.1997.0439zbMath0872.68026OpenAlexW2089272132WikidataQ100328979 ScholiaQ100328979MaRDI QIDQ1361883

Publication date: 16 September 1997

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/af0b6e11f66bebe3f0525fc31ccce7f309d74274

zbMATH Keywords

randomized algorithm decoding of Reed-Solomon codes maximum likelihood decoding algorithm polynomial time bounded algorithm

Mathematics Subject Classification ID

Cyclic codes (94B15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20) Decoding (94B35)

Related Items (89)

Soft decoding of short/medium length codes using ordered statistics for quantum key distribution ⋮ Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring ⋮ Weight distributions for projective binary linear codes from Weil sums ⋮ On algorithms to find \(p\)-ordering ⋮ Computing minimal interpolation bases ⋮ Decoding interleaved Reed-Solomon codes over noisy channels ⋮ Factors of low individual degree polynomials ⋮ Fast operations on linearized polynomials and their applications in coding theory ⋮ New lower bounds for the minimum distance of generalized algebraic geometry codes ⋮ Parallel Hashing via List Recoverability ⋮ Parameter choices and a better bound on the list size in the Guruswami-Sudan algorithm for algebraic geometry codes ⋮ On the Error-Correcting Radius of Folded Reed–Solomon Code Designs ⋮ Power Decoding of Reed–Solomon Codes Revisited ⋮ Cryptanalyzing the polynomial-reconstruction based public-key system under optimal parameter choice ⋮ On the error distance of extended Reed-Solomon codes ⋮ Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes ⋮ Reconstructive dispersers and hitting set generators ⋮ List Decoding of Binary Codes–A Brief Survey of Some Recent Results ⋮ On building fine-grained one-way functions from strong average-case hardness ⋮ List decoding of repeated codes ⋮ ECC\(^2\): error correcting code and elliptic curve based cryptosystem ⋮ A Decoding Approach to Reed–Solomon Codes from Their Definition ⋮ A modified Guruswami-Sudan algorithm for decoding Reed-Solomon codes ⋮ List-decoding Barnes-Wall lattices ⋮ NP-Hardness of Reed--Solomon Decoding, and the Prouhet--Tarry--Escott Problem ⋮ On one-round reliable message transmission ⋮ Multi-trial Guruswami-Sudan decoding for generalised Reed-Solomon codes ⋮ List and unique error-erasure decoding of interleaved Gabidulin codes with interpolation techniques ⋮ On deep holes of standard Reed-Solomon codes ⋮ Error-Correcting Codes Against Chosen-Codeword Attacks ⋮ Collision-resistance from multi-collision-resistance ⋮ Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes ⋮ Fast Kötter-Nielsen-Høholdt interpolation over skew polynomial rings and its application in coding theory ⋮ Efficient NIZKs from LWE via polynomial reconstruction and ``MPC in the head ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Generalized Singleton Bound and List-Decoding Reed–Solomon Codes Beyond the Johnson Radius ⋮ On the error-correcting pair for MDS linear codes with even minimum distance ⋮ Unnamed Item ⋮ List decoding of maximal order codes over number fields ⋮ Asymptotic single-trial strategies for GMD decoding with arbitrary error-erasure tradeoff ⋮ On Reed-Solomon codes ⋮ Bounds on collaborative decoding of interleaved Hermitian codes and virtual extension ⋮ Variations on Muchnik's conditional complexity theorem ⋮ On multi-trial Forney-Kovalev decoding of concatenated codes ⋮ Polynomial root finding over local rings and application to error correcting codes ⋮ Amplification and Derandomization without Slowdown ⋮ Decoding interleaved Reed-Solomon codes beyond their joint error-correcting capability ⋮ A Syndrome Formulation of the Interpolation Step in the Guruswami-Sudan Algorithm ⋮ Efficient List Decoding of Explicit Codes with Optimal Redundancy ⋮ Generalized Sudan’s List Decoding for Order Domain Codes ⋮ List decoding of Reed-Solomon codes from a Gröbner basis perspective ⋮ Finding smooth integers in short intervals using CRT decoding ⋮ Group homomorphisms as error correcting codes ⋮ Gröbner basis approach to list decoding of algebraic geometry codes ⋮ ON LIST DECODING OF WAVELET CODES OVER FINITE FIELDS OF CHARACTERISTIC TWO ⋮ Parameter choices on Guruswami-Sudan algorithm for polynomial reconstruction ⋮ An application of bivariate polynomial factorization on decoding of Reed-Solomon based codes ⋮ Big data interpolation using functional representation ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ List decoding of number field codes ⋮ Key equations for list decoding of Reed-Solomon codes and how to solve them ⋮ Correlated algebraic-geometric codes: Improved list decoding over bounded alphabets ⋮ Pseudorandom generators without the XOR lemma ⋮ Extractors from Reed-Muller codes ⋮ List decodability at small radii ⋮ Privacy-preserving verifiable delegation of polynomial and matrix functions ⋮ New constructions for IPP codes ⋮ Power decoding Reed-Solomon codes up to the Johnson radius ⋮ Unnamed Item ⋮ Explicit list-decodable codes with optimal rate for computationally bounded channels ⋮ On 2-dimensional insertion-deletion Reed-Solomon codes with optimal asymptotic error-correcting capability ⋮ Fitting algebraic curves to noisy data ⋮ Pseudo-random generators for all hardnesses ⋮ The Vanishing Ideal of a Finite Set of Points with Multiplicity Structures ⋮ List decoding of Hermitian codes using Gröbner bases ⋮ Optimal Rate List Decoding via Derivative Codes ⋮ Improvements on the Johnson bound for Reed-Solomon codes ⋮ Simplified High-Speed High-Distance List Decoding for Alternant Codes ⋮ Noisy Chinese remaindering in the Lee norm ⋮ Efficient systolic multiplications in composite fields for cryptographic systems ⋮ Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition ⋮ A note on good permutation codes from Reed-Solomon codes ⋮ Reconstructing Algebraic Functions from Mixed Data ⋮ On error distance of Reed-Solomon codes ⋮ Power error locating pairs ⋮ On deep holes of generalized Reed-Solomon codes ⋮ List-Decoding with Double Samplers ⋮ Scalable secure storage when half the system is faulty ⋮ Gröbner basis solutions of constrained interpolation problems

Cites Work

This page was built for publication: Decoding of Reed Solomon codes beyond the error-correction bound