Beyond the Guruswami-Sudan (and Parvaresh-Vardy) Radii: Folded Reed-Solomon, Multiplicity and Derivative Codes
share
The classical family of Reed-Solomon codes consist of evaluations of polynomials over the finite field 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, multiplicity codes and 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.
READ FULL TEXT