Index Coding, Network Coding and Broadcast with Side-Information

Index coding, the problem of efficient broadcast to many receivers with side-infomation, is a rich and active research area. It has applications to a range of multi-user broadcast scenarios such as video-on-demand and satellite communications. It has attracted significant theoretical interest both as a hard problem in its own right and due to its connections to other network capacity problems. The central problem of index coding, that of determining the optimal rate of an index code, is still open. We describe recent advances on the index coding problem and its generalizations in the context of broadcast with side-information. The two main approaches to bounding the optimal rate of an index code, namely rank-minimization methods and linear programming models, are discussed in detail. The latter of these, based on graph-theoretical ideas in the classical case, can be extended even to generalizations of the index coding problem for which there is no associated side-information hypergraph. We discuss error-correction in the index coding problem, the corresponding bounds on the optimal transmission rate and decoding algorithms. We also illustrate the connections to network coding, interference alignment and coded caching.