Venkatesan Guruswami and Atri Rudra

Well, clearly one needs at least *k* correct packets. In this paper,
we present an an encoding scheme that attains this information-theoretic limit:
for any desired *e> 0*, it enables correct decoding of the message
(in an error-recovery model called *list decoding*) as long as at least
*k(1+e)* packets are received intact. The location of the correct
packets and the errors on the remaining packets can be picked adversarially by
the channel.

This achieves the optimal trade-off between redundancy and error-resilience for a worst-case noise model where the channel can corrupt the transmitted symbols arbitrarily subject to a bound on the total number of errors. Previously, such results were known for weaker stochastic noise models. This work closes one of the central open questions in algorithmic coding theory.

Additionally, our codes are very simple to describe: they are certain "folded" Reed-Solomon codes, which are just the well known Reed-Solomon codes, but viewed as a code over a larger alphabet via a bundling together of codeword symbols. Reed-Solomon codes are used in modern day storage devices (like CDs and DVDs). This connection enhances the practical aspect of our work.

- IEEE Transactions on Information Theory, 54(1), Pgs. 135 - 150. January 2008. [PDF].
- Preliminary version in Proceedings of the 38th ACM Symposium on Theory of Computing
(STOC), under the title
*Explicit Capacity-Achieving List-Decodable Codes*, Pgs. 1-10. May 2006. [PDF] - Invited paper in Proceedings of the Forty-Fourth Annual Allerton Conference on Communication, Control, and Computing. September 2006. [PDF]
- Electronic Colloquium on Computational Complexity (ECCC) Tech Report TR05-133. November 2005.

- The STOC06 version was highlighted, along with two other papers in the a news release for STOC 2006 and in the ACM SIGACT Annual report for 2006.
- Bernard Chazelle, Coding and Computing Join Forces, Science Magazine. September 2007.