We present an improved list decoding algorithm for decoding
Reed-Solomon codes. Given an arbitrary string of length n, the
list decoding problem is that of finding all codewords within a
specified Hamming distance from the input string.

It is well-known that this decoding problem for Reed-Solomon
codes reduces to the following curve-fitting problem over a field
F: Given n points {(x_i.y_i)}_{i=1}^n, x_i,y_i in F, and a
degree parameter k and error parameter e, find all univariate
polynomials p of degree at most k such that y_i= p(x_i) for all
but at most e values of i in {1 .. n}. Our algorithm solves this
problem for e < n - sqrt{kn}, which improves over the previous
best result due to Sudan [FOCS '96], for every choice of k and n.
Previously it was known how to correct approximately max {n -
sqrt{2kn}, (n-k)/2} errors. Of particular interest is the case of
k/n > 1/3, where the result yields the first asymptotic
improvement over the classical Berlekamp-Massey algorithm.

The algorithm generalizes to decode other codes as well. In
particular it immediately yields a list decoding problem for
alternant codes that corrects up to n - sqrt{n(n-d')} errors,
where $n$ is the block length and $d'$ is the designed distance
of the code. Using the methods of Shokrollahi and Wasserman,
[STOC '98], we also extend our algorithm to the case of
algebraic-geometric codes, and solve the list decoding problem
for up to n-sqrt{n(n-d')} errors, where n and d' are as above.
This improves over the previous bound of n-sqrt{2n(n-d')}-g+1
where $g$ denotes the genus of the algebraic curve underlying the
code. We also present some other consequences of our algorithm
including a solution to a weighted curve fitting problem, which
may be of use in soft-decision decoding algorithms for Reed-
Solomon codes.