Article

Optimal rate list decoding via derivative codes

Authors:

APPROX'11/RANDOM'11: Proceedings of the 14th international workshop and 15th international conference on Approximation, randomization, and combinatorial optimization: algorithms and techniques

Pages 593 - 604

Published: 17 August 2011 Publication History

Publisher Site

Abstract

The classical family of [n, k]_q Reed-Solomon codes over a field F_q consist of the evaluations of polynomials f ∈ 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) 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.

References

[1]

Bombieri, E., Kopparty, S.: List decoding multiplicity codes (2011) (manuscript)

Google Scholar

[2]

Gemmell, P., Sudan, M.: Highly resilient correctors for multivariate polynomials. Information Processing Letters 43(4), 169-174 (1992)

Digital Library

Google Scholar

[3]

Guruswami, V.: List decoding with side information. In: Proceedings of the 18th IEEE Conference on Computational Complexity (CCC), pp. 300-309 (2003)

Crossref

Google Scholar

[4]

Guruswami, V.: Algorithmic Results in List Decoding. Foundations and Trends in Theoretical Computer Science (FnT-TCS), vol. 2. NOWpublishers (January 2007)

Digital Library

Google Scholar

[5]

Guruswami, V.: Cyclotomic function fields, Artin-Frobenius automorphisms, and list error-correction with optimal rate. Algebra and Number Theory 4(4), 433-463 (2010)

Crossref

Google Scholar

[6]

Guruswami, V.: Linear-algebraic list decoding of folded Reed-Solomon codes. In: Proceedings of the 26th IEEE Conference on Computational Complexity (June 2011)

Digital Library

Google Scholar

[7]

Guruswami, V., Rudra, A.: Limits to list decoding Reed-Solomon codes. IEEE Transactions on Information Theory 52(8), 3642-3649 (2006)

Digital Library

Google Scholar

[8]

Guruswami, V., Rudra, A.: Explicit codes achieving list decoding capacity: Errorcorrection up to the Singleton bound. IEEE Transactions on Information Theory 54(1), 135-150 (2008)

Digital Library

Google Scholar

[9]

Guruswami, V., Sudan, M.: Improved decoding of Reed-Solomon and Algebraicgeometric codes. IEEE Transactions on Information Theory 45(6), 1757-1767 (1999)

Digital Library

Google Scholar

[10]

Kopparty, S., Saraf, S., Yekhanin, S.: High-rate codes with sublinear-time decoding. Electronic Colloquium on Computational Complexity, TR10-148 (2010)

Google Scholar

[11]

Parvaresh, F., Vardy, A.: Correcting errors beyond the Guruswami-Sudan radius in polynomial time. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 285-294 (2005)

Digital Library

Google Scholar

[12]

Sudan, M.: Decoding of Reed-Solomon codes beyond the error-correction bound. Journal of Complexity 13(1), 180-193 (1997)

Digital Library

Google Scholar

[13]

Vadhan, S.: Pseudorandomness. Foundations and Trends in Theoretical Computer Science (FnT-TCS). NOW publishers (2010) (to appear) Draft available at, http://people.seas.harvard.edu/~salil/pseudorandomness/

Google Scholar

[14]

Welch, L.R., Berlekamp, E.R.: Error correction of algebraic block codes. US Patent Number 4, 633, 470 (December 1986)

Google Scholar

Cited By

View all

Kopparty SSaraf SYekhanin S(2014)High-rate codes with sublinear-time decodingJournal of the ACM10.1145/262941661:5(1-20)Online publication date: 8-Sep-2014
https://dl.acm.org/doi/10.1145/2629416
Dvir ZLovett SKarloff HPitassi T(2012)Subspace evasive setsProceedings of the forty-fourth annual ACM symposium on Theory of computing10.1145/2213977.2214010(351-358)Online publication date: 19-May-2012
https://dl.acm.org/doi/10.1145/2213977.2214010
Guruswami VXing CKarloff HPitassi T(2012)Folded codes from function field towers and improved optimal rate list decodingProceedings of the forty-fourth annual ACM symposium on Theory of computing10.1145/2213977.2214009(339-350)Online publication date: 19-May-2012
https://dl.acm.org/doi/10.1145/2213977.2214009
Show More Cited By

Optimal rate list decoding via derivative codes

Recommendations

Folded codes from function field towers and improved optimal rate list decoding
STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computing

We give a new construction of algebraic codes which are efficiently list decodable from a fraction 1-R-ε of adversarial errors where R is the rate of the code, for any desired positive constant ε. The worst-case list size output by the algorithm is O(1/...
Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy

In this paper, we present error-correcting codes that achieve the information-theoretically best possible tradeoff between the rate and error-correction radius. Specifically, for every 0 < R < 1 and epsiv < 0, we present an explicit ...
List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound
STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing

We consider Reed-Solomon (RS) codes whose evaluation points belong to a subfield, and give a linear-algebraic list decoding algorithm that can correct a fraction of errors approaching the code distance, while pinning down the candidate messages to a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

APPROX'11/RANDOM'11: Proceedings of the 14th international workshop and 15th international conference on Approximation, randomization, and combinatorial optimization: algorithms and techniques

August 2011

699 pages

ISBN:9783642229343

Editors:
Leslie Ann Goldberg
University of Liverpool, Department of Computer Science, Liverpool, UK
,
Klaus Jansen
University of Kiel, Department of Computer Science, Kiel, Germany
,
R. Ravi
Carnegie Mellon University, Pittsburgh, PA
,
José D. P. Rolim
University of Geneva, Carouge, Switzerland

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 17 August 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kopparty SSaraf SYekhanin S(2014)High-rate codes with sublinear-time decodingJournal of the ACM10.1145/262941661:5(1-20)Online publication date: 8-Sep-2014
https://dl.acm.org/doi/10.1145/2629416
Dvir ZLovett SKarloff HPitassi T(2012)Subspace evasive setsProceedings of the forty-fourth annual ACM symposium on Theory of computing10.1145/2213977.2214010(351-358)Online publication date: 19-May-2012
https://dl.acm.org/doi/10.1145/2213977.2214010
Guruswami VXing CKarloff HPitassi T(2012)Folded codes from function field towers and improved optimal rate list decodingProceedings of the forty-fourth annual ACM symposium on Theory of computing10.1145/2213977.2214009(339-350)Online publication date: 19-May-2012
https://dl.acm.org/doi/10.1145/2213977.2214009
Guruswami VNarayanan SWang CGoldwasser S(2012)List decoding subspace codes from insertions and deletionsProceedings of the 3rd Innovations in Theoretical Computer Science Conference10.1145/2090236.2090252(183-189)Online publication date: 8-Jan-2012
https://dl.acm.org/doi/10.1145/2090236.2090252

Abstract

References

Cited By

Recommendations

Folded codes from function field towers and improved optimal rate list decoding

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

List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations