Optimal Rate List Decoding via Derivative Codes

DOI10.1007/978-3-642-22935-0_50MaRDI QIDQ3088129zbMATH OpenOpenAlexFDO

Authors Carol J. Wang, Venkatesan Guruswami

Publication date 17 August 2011

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

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

zbMATH Keywords

list error-correctionmultiplicity codesnoisy polynomial interpolationpseudorandomnessReed-Solomon codessubspace-evasive sets

Mathematics Subject Classification ID

Cyclic codes (94B15) Decoding (94B35)

Abstract: The classical family of $[n,k{]}_q$ Reed-Solomon codes over a field $F_q$ consist of the evaluations of polynomials $fin{F}_q[X]$ of degree $<k$ at $n$ distinct field elements. In this work, we consider a closely related family of codes, called (order $m$) {em derivative codes} and defined over fields of large characteristic, which consist of the evaluations of $f$ as well as its first $m-1$ formal derivatives at $n$ distinct field elements. For large enough $m$, we show that these codes can be list-decoded in polynomial time from an error fraction approaching $1-R$, where $R=k/(nm)$ is the rate of the code. This gives an alternate construction to folded Reed-Solomon codes for achieving the optimal trade-off between rate and list error-correction radius. Our decoding algorithm is linear-algebraic, and involves solving a linear system to interpolate a multivariate polynomial, and then solving another structured linear system to retrieve the list of candidate polynomials $f$. The algorithm for derivative codes offers some advantages compared to a similar one for folded Reed-Solomon codes in terms of efficient unique decoding in the presence of side information.

Recommendations

• Explicit list-decodable codes with optimal rate for computationally bounded channels
• Explicit List-decodable codes with optimal rate for computationally bounded channels
• scientific article; zbMATH DE number 7561729
• Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes
• Optimal rate algebraic list decoding using narrow ray class fields
• Efficient List Decoding of Explicit Codes with Optimal Redundancy
• On the complexity of suboptimal decoding for list and decision feedback schemes
• On the list decodability of random linear codes with large error rates
• scientific article; zbMATH DE number 4162826
• Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets (extended abstract)

Cites work

• Algorithmic Results in List Decoding
• Cyclotomic function fields, Artin-Frobenius automorphisms, and list error correction with optimal rate
• Decoding of Reed Solomon codes beyond the error-correction bound
• Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy
• High-rate codes with sublinear-time decoding
• Highly resilient correctors for polynomials
• Improved decoding of Reed-Solomon and algebraic-geometry codes
• Limits to List Decoding Reed–Solomon Codes

Cited in

(10)

• On 2-dimensional insertion-deletion Reed-Solomon codes with optimal asymptotic error-correcting capability
• On list decoding of certain \(\mathbb{F}_q\)-linear codes
• Simultaneous rational function reconstruction with errors: handling multiplicities and poles
• Group homomorphisms as error correcting codes
• Synchronization strings: list decoding for insertions and deletions
• A note on subspace evasive sets
• Folded codes from function field towers and improved optimal rate list decoding
• High-rate codes with sublinear-time decoding
• Hermite interpolation with error correction. Fields of zero or large characteristic and large error rate
• List-decodable Byzantine robust PIR: lower communication complexity, higher Byzantine tolerance, smaller list size

This page was built for publication: Optimal Rate List Decoding via Derivative Codes

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