[Colloquium] Guest Speaker announcement

[Ponda Barnes]

Guest Speaker
 
Presented by: Toyota Technological Institute at Chicago
 
 
Speaker: Atri Rudra
Speaker's home page: http://www.cs.washington.edu/homes/atri/
 
Date: Thursday, April 12, 2007
Time: 10:00
Location: TTI-C Conference room
 
 
Title: Error-correction with information-theoretically optimal data rate
 
 
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 channel can
choose the location of the correct packets and the errors adversarially.
 
This scheme achieves the optimal trade-off 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, sub linear
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.
 
If you have any questions or would like to meet the speaker, please contact
Ponda Barnes at pondabarnes at tti-c.org.
For future TTI-C talks and events, please go to
http://ttic.uchicago.edu/cal/month.php
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20070411/3ef3757b/attachment.htm