  Algebraic codes that achieve list decoding capacity were recently constructed
by a careful ``folding'' of the Reed-Solomon code. The ``low-degree'' nature of
this folding operation was crucial to the list decoding algorithm. We show how
such folding schemes conducive to list decoding arise out of the
Artin-Frobenius automorphism at primes in Galois extensions. Using this
approach, we construct new folded algebraic-geometric codes for list decoding
based on cyclotomic function fields with a cyclic Galois group. Such function
fields are obtained by adjoining torsion points of the Carlitz action of an
irreducible $M \in \F_q[T]$. The Reed-Solomon case corresponds to the simplest
such extension (corresponding to the case $M=T$). In the general case, we need
to descend to the fixed field of a suitable Galois subgroup in order to ensure
the existence of many degree one places that can be used for encoding.
  Our methods shed new light on algebraic codes and their list decoding, and
lead to new codes achieving list decoding capacity. Quantitatively, these codes
provide list decoding (and list recovery/soft decoding) guarantees similar to
folded Reed-Solomon codes but with an alphabet size that is only
polylogarithmic in the block length. In comparison, for folded RS codes, the
alphabet size is a large polynomial in the block length. This has applications
to fully explicit (with no brute-force search) binary concatenated codes for
list decoding up to the Zyablov radius.
