Beyond the Guruswami-Sudan (and Parvaresh-Vardy) Radii: Folded Reed-Solomon, Multiplicity and Derivative Codes

The classical family of Reed-Solomon codes consist of evaluations of polynomials over the finite field $\mathbb{F}_q$ of degree less than $k$, at $n$ distinct field elements. These are arguably the most widely used and studied codes, as they have both erasure and error-correction capabilities, among many others nice properties. In this survey we study closely related codes, folded Reed-Solomon codes, which are the first constructive codes to achieve the list decoding capacity. We then study two more codes which also have this feature, \textit{multiplicity codes} and \textit{derivative codes}. Our focus for the most part are the list decoding algorithms of these codes, though we also look into the local decodability of multiplicity codes.

• Publication year

  2020

• Venue

  arXiv.org

• Publication date

  2020-03-11

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 2003.05400
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Computations with p-adic numbers

  2017cited by this paper
• Some remarks on multiplicity codes

  2015cited by this paper
• Linear-Algebraic List Decoding for Variants of Reed–Solomon Codes

  2013cited by this paper
• List-Decoding Multiplicity Codes

  2012influential reference
• A Note on Subspace Evasive Sets

  2012influential reference
• High-rate codes with sublinear-time decoding

  2011cited by this paper
• Linear-Algebraic List Decoding of Folded Reed-Solomon Codes

  2011cited by this paper
• Subspace evasive sets

  2011influential reference
• Optimal Rate List Decoding via Derivative Codes

  2011influential reference
• Interpolation and List Decoding of Algebraic Codes

  2010cited by this paper
• Folded Algebraic Geometric Codes From Galois Extensions

  2009cited by this paper
• Decoding Folded Reed-Solomon Codes Using Hensel-Lifting

  2009cited by this paper
• The p-adic Numbers

  2009cited by this paper
• Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers

  2009cited by this paper
• The Berlekamp algorithm

  2009cited by this paper
• Hensel’s lemma

  2009cited by this paper
• Noisy Interpolating Sets for Low Degree Polynomials

  2008cited by this paper
• Artin automorphisms, cyclotomic function fields, and folded list-decodable codes

  2008cited by this paper
• Algorithmic Results in List Decoding

  2006cited by this paper
• Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy

  2005cited by this paper
• Correcting errors beyond the Guruswami-Sudan radius in polynomial time

  2005cited by this paper
• Reed-Solomon codes for correcting phased error bursts

  2003influential reference
• Improved decoding of Reed-Solomon and algebraic-geometric codes

  1998cited by this paper
• Decoding of Reed Solomon Codes beyond the Error-Correction Bound

  1997cited by this paper
• Modular andp-adic cyclic codes

  1995cited by this paper
• An introduction to the theory of numbers (5th edition) , by I. Niven, H. S. Zuckerman and H. L. Montgomery. Pp 529. £14·50. 1991. ISBN 0-471-5460031 (Wiley)

  1991cited by this paper
• Arithmetic of p-adic Modular Forms

  1988cited by this paper
• p-adic Numbers, p-adic Analysis, and Zeta-Functions

  1977cited by this paper
• Factoring polynomials over large finite fields*

  1970cited by this paper
• HENSEL'S LEMMA

  1957cited by this paper
• An Introduction to the Theory of Numbers

  1939cited by this paper

• No citing papers are available for this paper.