  In this paper we show that the Index Coding problem captures several
important properties of the more general Network Coding problem. An instance of
the Index Coding problem includes a server that holds a set of information
messages $X=\{x_1,...,x_k\}$ and a set of receivers $R$. Each receiver has some
side information, known to the server, represented by a subset of $X$ and
demands another subset of $X$. The server uses a noiseless communication
channel to broadcast encodings of messages in $X$ to satisfy the receivers'
demands. The goal of the server is to find an encoding scheme that requires the
minimum number of transmissions.
  We show that any instance of the Network Coding problem can be efficiently
reduced to an instance of the Index Coding problem. Our reduction shows that
several important properties of the Network Coding problem carry over to the
Index Coding problem. In particular, we prove that both scalar linear and
vector linear codes are insufficient for achieving the minimal number of
transmissions.
