Posted by: atri | April 24, 2011

Lecture 36: Folded Reed-Solomon codes

In Friday’s lecture, we started working our way towards an explicit code of rate R that can be list decoded from 1-R-\epsilon fraction of errors in polynomial time. Towards this end, we introduced the Folded Reed-Solomon codes and saw some intuition for why such codes can have better list decodability than Reed-Solomon codes. At the end we stated the very recent list decoding algorithm for Folded RS codes due to Guruswami.

On Monday, we will analyze the new list decoding algorithm.

Finally, here is a link to the survey (acm link) on list decoding algorithms that I mentioned in class on Friday.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s


%d bloggers like this: