Algorithmic Improvements to List Decoding of Folded Reed-Solomon Codes

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ε.

We present a deterministic decoder that runs in near-linear time O ε (n), improving upon the best-known runtime n Ω(1/ε) for decoding FRS codes. Prior to our work, no capacity achieving code was known whose deterministic decoding could be done in time O ε (n).

We also present a randomized decoder that runs in fully polynomial time poly(1/ε) • O(n), improving the best-known runtime exp(1/ε) • O(n) for decoding FRS codes. Again, prior to our work, no capacity achieving code was known whose decoding time depended polynomially on 1/ε.

Our results are based on improved pruning procedures for finding the list of codewords inside a constant-dimensional affine subspace.