  This letter investigates a new class of index coding problems. One sender
broadcasts packets to multiple users, each desiring a subset, by exploiting
prior knowledge of linear combinations of packets. We refer to this class of
problems as index coding with coded side-information. Our aim is to
characterize the minimum index code length that the sender needs to transmit to
simultaneously satisfy all user requests. We show that the optimal binary
vector index code length is equal to the minimum rank (minrank) of a matrix
whose elements consist of the sets of desired packet indices and side-
information encoding matrices. This is the natural extension of matrix minrank
in the presence of coded side information. Using the derived expression, we
propose a greedy randomized algorithm to minimize the rank of the derived
matrix.
