This paper is concerned with a new family of error-correcting codes
based on algebraic curves over finite fields, and list decoding
algorithms for them. The basic goal in the subject of list decoding is
to construct error-correcting codes $C$ over some alphabet $\Sigma$
which have good rate $R$, and at the same every Hamming ball of
(relative) radius $p$ has few codewords of $C$, and moreover these
codewords can be found in polynomial time.

The trade-off between the rate $R$ and the error-correction radius $p$
is a central one governing list decoding. Traditional ``unique
decoding'' algorithms can achieve $p = (1-R)/2$, and this was improved
in \cite{GS} to $p =1 - \sqrt{R}$ through a new list decoding
algorithm for Reed-Solomon (RS) codes. For several years, this
remained the best known trade-off between rate and list decoding
radius. In a recent breakthrough, Parvaresh and Vardy~\cite{PV} define
a variant of RS codes which can be list decoded beyond the
$1-\sqrt{R}$ radius for rates $R \le 1/16$.

We generalize the PV framework to algebraic-geometric
(AG) codes, of which RS codes are an important special case. This
shows that their framework applies to fairly general settings, and
also better elucidates the key algebraic concepts underlying the new
codes. Moreover, since AG codes of arbitrary block length exist over
{\em fixed} alphabets $\Sigma$, we are able to almost match the
trade-off between $p$ and $R$ obtained in \cite{PV} over alphabets of
{\em constant} size. In contrast, the PV codes have alphabet size that
is polynomially large in the block length.

Similar to list decoding algorithms for AG codes, our
encoding/decoding algorithms run in polynomial time assuming a natural
polynomial-size representation of the code. For codes based on a
specific ``optimal'' algebraic curve, we also present an expected
polynomial time algorithm to construct the requisite representation.