Algorithmic Improvements to List Decoding of Folded Reed-Solomon Codes

Abstract

Folded Reed-Solomon (FRS) codes are a well-studied family of codes, known for achieving list decoding capacity. In this work, we give improved deterministic and randomized algorithms for list decoding FRS codes of rate $R$ up to radius $1-R-\epsilon$. We present a deterministic decoder that runs in near-linear time ${\tilde{O}}_{\epsilon }(n)$, improving upon the best-known runtime $n^{\hat{I}\text{c◯}(1/\epsilon )}$ for decoding FRS codes. Prior to our work, no capacity achieving code was known whose deterministic decoding could be done in time ${\tilde{O}}_{\epsilon }(n)$. We also present a randomized decoder that runs in fully polynomial time $\mathrm{poly}(1/\epsilon )\cdot \tilde{O}(n)$, improving the best-known runtime $\exp (1/\epsilon )\cdot \tilde{O}(n)$ for decoding FRS codes. Again, prior to our work, no capacity achieving code was known whose decoding time depended polynomially on $1/\epsilon$. Our results are based on improved pruning procedures for finding the list of codewords inside a constant-dimensional affine subspace.

Fixed an error in Observation 2.15