Suppose you want to communicate a message of k packets on a noisy communication channel. So you judiciously encode it as a redundant collection of n = ck packets and transmit these. What is the fewest number of correct packets one needs to receive in order to have any hope of recovering the message?
Well, clearly one needs at least k correct packets. In this talk, I will describe recent work that gives an encoding scheme that attains this information-theoretic limit: for any desired eps > 0, it enables recovery of the message as long as at least k(1+eps) 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 (called "capacity") between redundancy and error-resilience for a malicious noise model where the channel can corrupt the transmitted symbols arbitrarily subject to a bound on the total number of errors. Previously, capacity-achieving error-correcting codes were only known for weaker, stochastic models of the channel noise.
These results are obtained in a error-recovery model called list decoding. The talk will introduce and motivate the problem of list decoding, and then give a peek into the algebraic ideas and constructions that lead to the above result. We will also describe some challenging questions that still remain open.
The talk will be self-contained. Based on joint work with Atri Rudra.