Abstract:

The construction of error-correcting codes that achieve the best
possible trade-off between information rate and the amount of errors
that can be corrected has been a long sought-after goal.  This talk
will survey some of our work on list decoding, culminating in the
construction of codes with the *optimal* rate for any desired error-
correction radius.  I will describe these codes (called folded Reed-
Solomon codes), and give a peek into the algebraic ideas underlying
their error-correction. Our decoder corrects a factor of two more
errors compared to the conventional algorithms used in every CD
player and desktop PC, as well as many other applications that impact
our daily lives. The newly discovered codes admit a "soft" decoding
algorithm that can utilize channel reliability estimates in a
powerful way.  This is an attractive feature in practice, and also
useful in concatenation schemes. Exploiting this, we construct the
best known binary codes for list decoding.

Over the years, list decodable codes have also found several elegant
applications extraneous to coding theory. I will mention a striking
recent example in this vein: a simple construction of unbalanced
bipartite graphs with near-optimal expansion properties.