Speaker: Atri Rudra
University of Washington
Monday, April 16, 2007
11:00 am - 12:00 pm
EBU3b 1202

ABSTRACT
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 scheme achieves the optimal trade-off (called "capacity") between redundancy and error-resilience for a malicious noise model in which 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 this talk I will introduce and motivate list decoding and then give an overview of our encoding scheme.

I will also briefly discuss my other work in game theory, sublinear algorithms, approximation algorithms and coding theory. In particular, I will talk about my results in profit maximizing auctions, lower bounds for data stream algorithms and rank aggregation.

BIO
Atri Rudra is a Ph.D. Candidate in the Department of Computer Science & Engineering at the University of Washington. He was a Research Staff Member at IBM India Research Labs from 2000-2002 and received his Bachelor's degree in Computer Science and Engineering from Indian Institute of Technology, Kharagpur. Atri's primary research interest is theoretical computer science. In particular, he is interested in theory of error-correcting codes, game theory and algorithmic mechanism design, approximation algorithms, computational complexity, probabilistically checkable proofs, cryptography, finite field theory and applications.