An error-correcting code provides a judicious way to encode messages
into codewords, incorporating enough redundancy in the process to
enable recovery of the message upon receipt of an erroneous
codeword. The fundamental trade-off in coding theory is the one
between the rate of the code (a measure of amount of redundancy
introduced) and the amount of errors that can be corrected. In this
talk, we will describe an explicit construction of codes that achieves
the optimal trade-off (called "capacity") for a worst-case/adversarial
noise model where the channel can corrrupt the codeword arbitrarily
subject to a bound on the total number of errors. Previously,
capacity-achieving codes were only known for weaker, stochastic models
of the channel noise.

Formally, for every 0 < R < 1 and eps > 0, we present an explicit
construction of codes of rate R (which encode R.n symbols into n
symbols) that can be *list decoded* in polynomial time from up to a
fraction (1-R-eps) of errors. Clearly, one needs at least Rn correct
symbols in the received word to have any hope of identifying the Rn
message symbols, so recovering from (R+eps)n correct symbols is
information-theoretically best possible. Our codes are simple to
describe: they are certain *folded* Reed-Solomon codes, which are just
Reed-Solomon codes, but viewed as a code over a larger alphabet by a
careful bundling of codeword symbols.

The talk will introduce and motivate the problem of list decoding, and
then give a peek into the algebraic ideas and constructions that lead
to the above result. We will also describe some consequences for
binary codes and challenging questions that remain open.

Based on joint work with Atri Rudra.