Faculty Candidate: Atri Rudra 

Time: 10:40 a.m., Tuesday, March 20
Place: CSE 404
Title: "Error-correction with information-theoretically optimal data
rate"

(Graduate students have half hour meeting with Dr. Rudra in room 305 at 3:00 p.m.)


Abstract:

      =======================================================================

      Error-correction with information-theoretically optimal data
      rate
      -----------------------------------------------------------------

      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 coding theory,
      game theory and approximation algorithms. In particular, I
      will talk about my results in profit maximizing auctions and
      rank aggregation.

      =======================================================================