Chapter 4: Index Coding and Coded Caching

Learning Objectives

• State the index coding problem: senders with full knowledge, receivers with side information, conflicting demands
• Construct the conflict graph / side-information graph of an index coding instance
• Relate index coding optimal rate to the fractional chromatic number of the conflict graph
• Recognize why general index coding is NP-hard and why MAN-type instances admit optimal linear codes
• Use clique-cover and local-chromatic-number heuristics to derive achievable rates
• See coded caching as a specific combinatorial family of index coding instances