# 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

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).

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 justReed-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:

94B35

Keywords: