List Decoding with Optimal Data Rate

Monday, April 16, 2007 - 10:40am - 11:30am
EE/CS 3-180
Venkatesan Guruswami (University of Washington)
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, I will describe an explicit construction of codes that achieves
the optimal trade-off between these parameters, for a worst-case noise model where the channel can corrrupt the codeword arbitrarily subject to a bound on the total number of errors.

Formally, for every 0 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 the problem of list decoding, and
then give a peek into the algebraic ideas and constructions that lead
to the above result. Time permitting, I will also describe some challenging questions concerning algebraic-geometric codes that, if resolved, could improve the decoding complexity as one approaches the optimal trade-off.

Based on joint work with Atri Rudra (UW).
MSC Code: