TIME: 1:30-2:30 pm,  Tuesday, October 7, 2008

PLACE: CSE 503  

SPEAKER: Eyal Lubetzky
         Microsoft Research

TITLE: Broadcasting with side-information


ABSTRACT: 
The index-coding problem describes a setting where a server holds a word,
consisting of n blocks, and wishes to transmit it to m target receivers.
Each receiver is interested in a particular block, and has
side-information in the form of some subset of the remaining blocks.
This problem has been studied in the context of Informed Source Coding on
Demand, and is related to other coding theoretic notions, such as Network
Coding.

I will describe some of the recent developments in this area, where we
applied various tools from extremal graph theory to obtain bounds on the
broadcast rates, and showed that there can be surprisingly large gaps
between them. This includes an example of the counterintuitive
direct-sum phenomenon in Information Theory.

Based on joint papers with Alon, Hassidim, Stav and Weinstein.