| |
|
| |
|
Venkat i Guruswami
University of Washington
List Decoding: What, Why and How?
April 13, 2006 11:15am
Abstract:
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 introduce and motivate a error-recovery model called list decoding under which one can attain this information-theoretic limit. Specifically, for any desired eps > 0, there is a coding scheme that 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. Depending on time, I'll give a peek into the algebraic ideas and constructions that lead to the above result. The talk will be self-contained.
If you have questions, or would like to meet the speaker, please contact Ponda at 4-1994 or pondabarnes@tti-c.org. For information on future TTI-C talks or events, please go to the TTI-C Events page.