Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, September 21, 2006, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Venkatesan Guruswami (Univ. of Washington)
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 an encoding scheme that attains this information-theoretic limit: for any desired eps > 0, it enables correct decoding of the message (in an error-recovery model called list decoding) 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 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. 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.
Joint work with Atri Rudra.
Automatic MiSe System Software Version 1.4803M | admin login