TIME: 1:30-2:20 pm,  October 10, 2006

PLACE: CSE 403

TITLE:   INDEX coding with side information

SPEAKER:  T.S. Jayram
          IBM Research, Almaden  (on sabbatical at University of Washington)
 

ABSTRACT:

Motivated by a problem of transmitting data over broadcast channels
(Birk and Kol, INFOCOM 1998), we study the following coding problem: a
sender holds a n-bit input x and wishes to broadcast a single message
to n receivers R_1,...,R_n so that each receiver R_i can recover the
bit i-th bit of x. Each receiver R_i has prior side information about
x, induced by a directed graph G on n nodes; receiver R_i knows the
bits of x in the positions {j | (i,j) is an edge of G}. We call
encoding schemes that achieve this goal INDEX codes for {0,1}^n with
side information graph G.

In this talk, we identify a measure on graphs, the minrank, which we
conjecture to exactly characterize the minimum length of INDEX
codes. We resolve the conjecture for certain natural classes of
graphs. For arbitrary graphs, we show that the minrank bound is tight
for both linear codes and certain classes of non-linear codes. For the
general problem, we obtain a (weaker) lower bound that the length of
an INDEX code for any graph G is at least the size of the maximum
acyclic induced subgraph of G.