Atri Rudra

Suppose you want to communicate k packets over a noisy communication channel. This is a common scenario when transmitting data over any real world channel such as the Internet or the telephone line. In order to tolerate errors, you transmit a redundant collection of n=c*k packets. When can you communicate reliably despite the adverse effects of the noisy channel? That is, when can the receiver recover the original message even in the presence of corrupted packets?

Clearly, the receiver must receive at least k correct packets to have any hope of recovering the original message. In this talk, I will describe an efficient encoding (and decoding) scheme that achieves this information theoretical limit: for any eps>0, the receiver can recover the original message as long as (1+eps)*k packets are not corrupted. The location of the correct packets and the errors can be chosen 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. These results are obtained in an error-recovery model called list decoding.

In the second part of the talk I will focus on some important challenges that are yet to be resolved and describe some recent developments that make some (small) progress towards addressing those questions.

The talk will be self-contained and is based on joint works with Venkat Guruswami (U. of Washington)

Monday, September 24, 2007 4:00 PM 5130 Upson Hall		Theory Seminar Fall 2007 CS 789
	Atri Rudra University at Buffalo
	Recovering Data in Presence of Malicious Errors
	Suppose you want to communicate k packets over a noisy communication channel. This is a common scenario when transmitting data over any real world channel such as the Internet or the telephone line. In order to tolerate errors, you transmit a redundant collection of n=ck packets. When can you communicate reliably despite the adverse effects of the noisy channel? That is, when can the receiver recover the original message even in the presence of corrupted packets? Clearly, the receiver must receive at least k correct packets to have any hope of recovering the original message. In this talk, I will describe an efficient encoding (and decoding) scheme that achieves this information theoretical limit: for any eps>0, the receiver can recover the original message as long as (1+eps)k packets are not corrupted. The location of the correct packets and the errors can be chosen 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. These results are obtained in an error-recovery model called list decoding. In the second part of the talk I will focus on some important challenges that are yet to be resolved and describe some recent developments that make some (small) progress towards addressing those questions. The talk will be self-contained and is based on joint works with Venkat Guruswami (U. of Washington)