We will describe a linear-algebraic list decoder for Reed-Solomon codes when the evaluation points belong to a subfield. The algorithm is able to correct a fraction of worst-case errors approaching the information-theoretically maximum limit of 1-R where R is the rate of the code. The methods extend to algebraic-geometric codes, as well as Gabidulin's rank-metric analog of RS codes.

The algorithm first pins down candidate solutions to a subspace of dimension a constant factor smaller than the code dimension. By restricting the message coefficients to belong to a "subspace design," one can efficiently prune the subspace to a small list of close-by codewords.

For the rank-metric, our work gives the first construction of positive rate codes list decodable beyond half the distance.