Index Coding With Side Information

Motivated by a problem of transmitting supplemental data over broadcast channels (Birk and Kol, INFOCOM 1998), we study the following coding problem: a sender communicates with n receivers R-1, ... ,R-n. He holds an input x is an element of {0, 1}(n) and wishes to broadcast a single message so that each receiver R-i can recover the bit x(i). Each R-i has prior side information about x, induced by a directed graph G on n nodes; R-i knows the bits of x in the positions {j vertical bar (i, j) is an edge of G }. G is known to the sender and to the receivers. We call encoding schemes that achieve this goal INDEXcodes for {0, 1}(n) with side information graph G. In this paper we identify a measure on graphs, the minrank, which exactly characterizes the minimum length of linear and certain types of nonlinear INDEX codes. We show that for natural classes of side information graphs, including directed acyclic graphs, perfect graphs, odd holes, and odd anti-holes, minrank is the optimal length of arbitrary INDEX codes. For arbitrary INDEX codes and arbitrary graphs, we obtain a lower bound in terms of the size of the maximum acyclic induced subgraph. This bound holds even for randomized codes, but has been shown not to be tight.