List decoding of algebraic-geometric codes

We generalize Sudan's results for Reed-Solomon codes to the class of algebraic-geometric codes, designing algorithms for list decoding of algebraic geometric codes which can decode beyond the conventional error-correction bound (d - 1)/2, d being the minimum distance of the code. Our main algorithm is based on an interpolation scheme and factorization of polynomials over algebraic function fields, For the latter problem we design a polynomial-time algorithm and show that the resulting overall list-decoding algorithm runs in polynomial time under some mild conditions. Several examples are included.