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.