A Hensel Lifting for List Decoding

This article describes an algorithmic improvement on Sudan’s algorithm for Reed-Solomon codes and its generalization to algebraic-geometric codes by Shokrollahi and Wasserman. Instead of completely factoring the interpolation polynomial over the function field of the curve, we compute fast sufficiently many coefficients of the p-adic expansion of the functions corresponding to codewords we are looking for, using Newton’s method.

This is a joint work with Daniel Augot, published in IEEE Transactions on Information Theory, vol. 46, n°7, pp. 2605-2614, 2000. A preliminary version was available in the INRIA Research Report, n° 3532, November 1998.