Exercises

$t = 4 \cdot 1/4 = 1$. $R_{\text{MAN}} = 3/2 = 1.5$.

$s = 1$: $R \geq 1(1 - 1/4) = 0.75$. $s = 2$: $\lfloor 4/2\rfloor = 2$, $R \geq 2(1 - 1/2) = 1$. $s = 3$: $\lfloor 4/3\rfloor = 1$, $R \geq 3(1-1) = 0$. $s = 4$: $R \geq 4(1-1) = 0$. Max: 1.

Gap = MAN/cut-set = 1.5/1 = 1.5. MAN exceeds the cut-set bound by 50% — the converse is loose here but not hopelessly so.

The cut-set proof bounds $\mathrm{H}(\mathcal{Z}_1, \ldots, \mathcal{Z}_s) \leq sMF$ using the fact that each cache has at most $MF$ bits of entropy. This inequality holds whether the cache contents are raw file bits (uncoded placement) or arbitrary functions of the files (coded placement). The argument is placement-agnostic, which is why it cannot tightly capture the uncoded/coded distinction. The YMA '18 converse does distinguish, by using a symmetry argument that only applies under uncoded placement.

$M = 0$: $R_{\text{MAN}} = 5$, cut-set (s=5): 5. Gap: 1. $M = 1$: $t = 1, R = 4/2 = 2$, cut-set max at s = 2: $\lfloor 5/2 \rfloor = 2$, $2(1 - 1/2) = 1$; s=3: 1(1-1/1)=0... max overall: 1 at s=2? Wait: s=4: $\lfloor 5/4\rfloor=1$, $4(1-1)=0$. Recheck s=1: $1(1-1/5)=0.8$. s=2: 1. s=3: 0. Max = 1. Gap 2. YMA matches MAN (2). $M = 2$: $t = 2, R = 3/3 = 1$, cut-set: s=2, $2(1-2/2)=0$; s=1, $0.6$. Max = 0.6. YMA says $R^* = 1$. $M = 3, 4, 5$: left as straightforward exercise.

The cut-set is loose at $M = 1, 2$; YMA '18 confirms that even under uncoded placement, $R = R_{\text{MAN}}$ is optimal. The gap between cut-set and YMA comes from tighter entropy bounds in the YMA argument.

$K = 20, N = 30$: worst $N_e = 20$ (all users distinct). $K = 30, N = 20$: worst $N_e = 20$ (every file requested at least once).

When $K > N$, some demand coincidences are forced (pigeonhole); the worst is when coincidences are minimized (each file requested $\lceil K/N \rceil$ times).

$\rho$ is the fraction of the file that is common across all files in the library. $\rho = 0$: all files are independent (MAN baseline). $\rho = 1$: all files are identical — the library effectively has only 1 file, and once all users cache a fraction $M/N$ of it (they need just one file's worth), delivery is trivial. Formally: WTJC rate $\to$ the rate of broadcasting the common part, which is the difference between what users cache and the whole file — approaching zero when caches can store the (single) file.

$R \geq K(1 - M/\lfloor N/K \rfloor)$. For $K \leq N$, $\lfloor N/K \rfloor = \lfloor N/K \rfloor$. For $K = N$: $\lfloor 1 \rfloor = 1$, so $R \geq K(1 - M)$.

$R_{\text{MAN}}(t) = (K - t)/(t + 1)$ at $t = KM/N = M$. Cut-set at $s = K$: $K(1 - M)$. Ratio MAN/cut-set = $(K - M)/((M + 1) K (1 - M))$. For $M = 1$, $K = 5$: MAN = 2, cut-set = 0. Hmm, cut-set becomes tight only at $M = 0$ and $M = 1$; in between it is weaker than other $s$ choices.

Fix worst-case demand $\mathbf{d} = (d_1, \ldots, d_K)$. For any permutation $\pi: [K] \to [K]$, the demand $\mathbf{d}^\pi = (d_{\pi(1)}, \ldots, d_{\pi(K)})$ has the same type (same histogram of distinct demands). Uncoded placement is invariant under relabeling: $\mathcal{Z}_k^\pi = \mathcal{Z}_{\pi(k)}$.

The rate for $\mathbf{d}^\pi$ equals the rate for $\mathbf{d}$ under the permuted scheme (just with users relabeled). Averaging over all permutations: the average rate equals the rate of the symmetric scheme, which is the MAN rate under this demand type.

Since the worst-case rate is at least the average rate, and the average equals the MAN rate, any scheme's worst-case rate is at least the MAN rate. Combined with MAN achievability, the two are equal. $\blacksquare$ (This is the high-level structure; the full YMA '18 proof requires care with finite $F$ and non-integer $t$.)

All users want the common component (every file has it), so a single broadcast suffices. The broadcast size is $(1 - M_c) \cdot \rho F$ bits if users cache fraction $M_c$ of the common part. Rate contribution: $\rho \cdot (1 - M_c)$ files.

Variants are independent across files. Apply MAN with $K$ users, $N$ variants, per-user cache $M_v = M - M_c \rho/N_{\text{variant}}$. Adjusted memory ratio $\mu_v = M_v/(N(1 - \rho))$ if we reinterpret variants as a reduced library. Rate contribution: $(1-\rho) \cdot K(1-\mu_v)/(1+K\mu_v)$.

The total rate is a convex combination; taking the derivative with respect to $M_c$ and setting to zero yields the optimal split. In closed form for symmetric libraries: $M_c^* \approx M/(1 + (K-1)\rho)$ balances the two terms.

$M = 0$: MAN rate = $K$. Cut-set with $s = K$: $R \geq K(1 - 0/1) = K$. Tight. $M = N$: MAN rate = 0. Cut-set trivially 0. Tight.

For $K = N$: at $M = iN/K = i$ for integer $i \in \{0, 1, \ldots, K\}$, MAN rate $= (K - i)/(i + 1)$. Cut-set with $s = K/(i+1)$ (when integer): matches after algebra. Generally, the cut-set is tight at the integer-$t$ MAN operating points when $K \mid N$.

For arbitrary $K, N$, the cut-set bound is tight at MAN integer-$t$ points up to floor corrections; the YMA '18 bound (tighter) is always tight. The cut-set loses tightness when $s$ and $N/s$ are "misaligned."

Type is the full histogram. $\mathbf{d}_1 = (1,2,1,2)$ has type $(2, 2, 0, \ldots)$ and $N_e = 2$. $\mathbf{d}_2 = (1,2,3,4)$ has type $(1,1,1,1,\ldots)$ and $N_e = 4$. Different types, different $N_e$.

For $K = 6$: $\mathbf{d}_1 = (1,1,1,2,2,2)$ has type $(3,3,0,\ldots)$ and $N_e = 2$. $\mathbf{d}_2 = (1,1,1,1,1,2)$ has type $(5,1,0,\ldots)$ and $N_e = 2$. MAN delivers the same number of subfiles in both cases (worst case per type), but the number of distinct missing-subfile index sets can differ, so rate may differ slightly.

Fix an uncoded placement scheme. For each permutation $\pi \in S_K$, the demand vector $\mathbf{d}^\pi = (\pi(1), \ldots, \pi(K))$ is a worst-case demand (all distinct). The scheme, with user labels permuted, produces rate $R^\pi$.

Because uncoded placement stores raw bits symmetrically, the scheme after permutation yields the same rate: $R^\pi = R$ for all $\pi$.

Consider the delivery messages across all $K!$ permutations. By a combinatorial counting argument over the entropies involved (done explicitly in the YMA '18 paper), the average rate is at least $(K-i)/(i+1)$ when $M = iN/K$.

Since the average rate $\geq (K-i)/(i+1)$ and all $R^\pi$ are equal to the same $R$, we have $R \geq (K-i)/(i+1)$. $\blacksquare$

At $t = 1$: $R = 2/2 = 1$. At $t = 2$: $R = 1/3$. $M = 1.5 = 0.5 \cdot 1 + 0.5 \cdot 2$, so $\alpha = 0.5$. Shared rate: $0.5 \cdot 1 + 0.5 \cdot 1/3 = 2/3 \approx 0.667$.

Place user 1's cache: $(W_1[1..F/3], W_2[1..F/3] \oplus W_3[1..F/3])$ (half the bits of $W_1$, plus one parity bit of $W_2, W_3$). Similar for users 2, 3.

With careful construction (see GV-Tian '18 §V), the worst-case rate becomes $R \approx 0.625$, beating the MAN memory-shared rate by about 6%. This is the first known coded-placement improvement for $K = 3$.

The construction does not generalize to arbitrary $K, N$. It shows that some improvement is possible over MAN, but the YMA '18 result conjecturally still holds (with small constant-factor corrections) for the coded-placement regime. This is an area of active research.

Given $K, N, M, F$, the optimal coded-placement rate is $$R^*_{\text{coded}}(M) \;=\; \min_{\phi_1, \ldots, \phi_K} \max_{\mathbf{d}} \frac{1}{F} \mathrm{H}(X_\mathbf{d}(\mathcal{Z}_1, \ldots, \mathcal{Z}_K))$$ subject to $\mathrm{H}(\mathcal{Z}_k) \leq MF$ and decodability constraints. The optimization is over all measurable functions $\phi_k$, not just bit-wise placements.

• Cut-set bounds joint entropy of caches but does not exploit combinatorial structure of the delivery phase.
• Averaging arguments (YMA '18) rely on user-permutation symmetry, which holds for uncoded but not coded placements.
• LP bounds grow exponentially in $K$; no tractable tightening.
• Algebraic bounds (entropy region) yield trivial bounds matching cut-set. The missing ingredient is a new technique that captures the coded-placement gain without sacrificing the worst-case demand bound.

Proposed approaches in the literature:

1. Entropy-region computer search (Csiszár-Körner '11 style) — scales to $K \leq 4$.
2. Non-Shannon inequality-aided bounds — gains up to 4% for small $K$.
3. Symmetric-coded-placement restrictions (Tian-Chen '18) — prove MAN optimal under symmetry.
4. Construction-based attacks: find a scheme strictly better than MAN for general $(K, N, M)$.

Wan-Caire '21+ showed that demand-private coded caching achieves the same rate as non-private MAN, via an augmented scheme that uses shared randomness to mask demand-dependent quantities.

Whether privacy strictly reduces rate for general coded-placement schemes (beyond MAN) is open. For uncoded placement, privacy comes at zero rate cost.

See Ch 12 for the full treatment. The CommIT group (Wan, Sun, Ji, Tuninetti, Caire) produced the foundational results on private coded caching.

For Zipf demand with exponent $\alpha \in [0, 1]$, the expected worst-case rate is $R_{\text{exp}}^*(M, \alpha) = \Theta(K(1 - H_{M, \alpha}/H_{N, \alpha})/(1 + KM/N))$. The upper and lower bounds differ by a constant factor depending on $\alpha$.

Exact characterization of $R^*_{\text{exp}}(M, \alpha)$ is open. The Caire group's work (Ji-Tulino-Llorca-Caire 2017, Jin-Cui-Liu-Caire 2017, Zhang-Pedarsani-Ji 2015) gives order-optimal bounds but not exact results.

Non-uniform demand is the realistic case; solving this question would bridge the worst-case theory of this chapter with production CDN workloads. Among the most important open problems in coded-caching theory.