References & Further Reading

References

Y. Birk and T. Kol, Informed-source coding-on-demand (ISCOD) over broadcast channels, 1998
The paper that introduced the index coding problem. Motivated by satellite broadcast with side information; pre-dates coded caching by 16 years.
Z. Bar-Yossef, Y. Birk, T. S. Jayram, and T. Kol, Index Coding With Side Information, 2011
The information-theoretic formalization. Proves the minrank = linear broadcast rate characterization, and gives the chromatic / independence bounds on the non-linear rate.
M. A. Maddah-Ali and U. Niesen, Fundamental Limits of Caching, 2014
The coded caching paper. Notes the connection to index coding and derives the MAN rate via the (implicit) vertex-transitive conflict graph structure.
R. Peeters, Orthogonal representations over finite fields and the chromatic number of graphs, 1996
Proves NP-hardness of computing minrank over finite fields. Foundational for the complexity of linear index coding.
E. Lubetzky and U. Stav, Nonlinear Index Coding Outperforming the Linear Optimum, 2009
Constructs index coding instances where non-linear codes beat linear codes by arbitrarily large factors. Key reference for understanding the limits of XOR-based schemes.
A. Blasiak, R. Kleinberg, and E. Lubetzky, Broadcasting With Side Information: Bounding and Approximating the Broadcast Rate, 2013
Comprehensive study of LP relaxations and their gaps for index coding. Introduces the local chromatic number as a tighter upper bound than $\chi_f$ in some cases.
H. Maleki, V. R. Cadambe, and S. A. Jafar, Index Coding — An Interference Alignment Perspective, 2014
Connects index coding to interference alignment in wireless BC. Essential reading before Chapter 5 (multi-antenna coded caching).
K. Shanmugam and A. G. Dimakis, Bounding Multiple Unicasts through Index Coding and Locally Repairable Codes, 2014
Connects index coding to distributed storage. Locally repairable codes are relevant for placement phase design in Chapter 14.
F. Arbabjolfaei, B. Bandemer, Y.-H. Kim, E. Sasoglu, and L. Wang, On the capacity region for index coding, 2013
Studies the capacity region of multi-source index coding — relevant for multi-demand and multi-message extensions of MAN.
M. Ji, A. M. Tulino, J. Llorca, and G. Caire, Caching in Combination Networks, 2017
Caire group's extension of MAN to combination networks using index-coding tools. Foreshadows the graph-coloring delivery schemes of Chapter 14.
Z. Bar-Yossef, Y. Birk, T. S. Jayram, and T. Kol, Index coding with side information, 2006
Conference version of the 2011 Trans. IT paper, with some different algorithmic results.
T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley-Interscience, 2nd ed., 2006
For the information-theoretic setup (Fano, entropy bounds) underlying index-coding converses.
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979
Classical reference for graph chromatic number NP-hardness (used in the NP-completeness chain for index coding).