Prerequisites & Notation

Before You Begin

This chapter views coded caching through the lens of index coding — a classical problem in network information theory and combinatorial optimization. The required background is a little discrete mathematics and comfort with the delivery phase of Chapter 2.

The MAN delivery scheme and XOR coded multicast (Ch 2)(Review ch02)
Self-check: Can you state the XOR delivery formula $X_{\mathcal{S}'} = \bigoplus_{k \in \mathcal{S}'} W_{d_k, \mathcal{S}' \setminus \{k\}}$ ?
Basic graph theory: vertices, edges, chromatic number, cliques
Self-check: For a graph with independence number $\alpha(G) = 3$ , can you bound the chromatic number from below?
Linear codes and rank over finite fields
Self-check: Given a $k \times n$ generator matrix, can you state the corresponding code's rate and length?
NP-hardness and polynomial reductions (at a conceptual level)
Self-check: Can you sketch why chromatic number is NP-hard?
Fano's inequality and converse arguments(Review ch01)
Self-check: Can you use Fano to bound a decoding error probability from entropy?

Notation for This Chapter

Symbols for the index coding problem. Many coincide with coded caching notation where the two problems overlap.

Symbol	Meaning	Introduced
$G = (V, E)$	Conflict graph (or side-information graph) of an index coding instance	s02
$\chi(G)$	Chromatic number of $G$	s02
$\chi_f(G)$	Fractional chromatic number of $G$ (LP relaxation)	s02
$\alpha(G)$	Independence number of $G$	s02
$\omega(G)$	Clique number of $G$	s02
$\beta(G)$	Broadcast rate — optimal index coding rate on $G$	s02
$K$	Number of receivers / coded-caching users (context)	s01
$t$	Coded caching gain parameter $t = KM/N$	s04

← Ch 3 The Index Coding Problem