  The \emph{index coding} problem has recently attracted a significant
attention from the research community due to its theoretical significance and
applications in wireless ad-hoc networks. An instance of the index coding
problem includes a sender that holds a set of information messages
$X=\{x_1,...,x_k\}$ and a set of receivers $R$. Each receiver $\rho=(x,H)\in R$
needs to obtain a message $x\in X$ and has prior \emph{side information}
comprising a subset $H$ of $X$. The sender uses a noiseless communication
channel to broadcast encoding of messages in $X$ to all clients. The objective
is to find an encoding scheme that minimizes the number of transmissions
required to satisfy the receivers' demands with \emph{zero error}.
  In this paper, we analyze the relation between the index coding problem, the
more general network coding problem and the problem of finding a linear
representation of a matroid. In particular, we show that any instance of the
network coding and matroid representation problems can be efficiently reduced
to an instance of the index coding problem. Our reduction implies that many
important properties of the network coding and matroid representation problems
carry over to the index coding problem. Specifically, we show that \emph{vector
linear codes} outperform scalar linear codes and that vector linear codes are
insufficient for achieving the optimum number of transmissions.
