Chapter Summary

Chapter 15 Summary

Key Points

• 1.

  PIR with side info (§15.1): Wei-Banawan-Ulukus 2019 settled the capacity for $M$ uncoded prefetched files: $C_{\text{PIR-SI}}(N, K, M) = C_{\text{PIR}}(N, K - M)$ — Sun-Jafar's formula with $K$ replaced by the effective $K - M$.

• 2.

  Cache-aided PIR (§15.2): for uniformly-random uncoded prefetching with cache fraction $\gamma$, capacity is the binomial mixture $\sum_i \binom{K-1}{i}\gamma^i(1-\gamma)^{K-1-i} C_{\text{PIR}}(N, K-i)$. Monotone in $\gamma$, reaches $1$ at $\gamma = 1$.

• 3.

  CommIT contribution (§15.3 — Wan-Tuninetti-Caire 2021): optimal demand-private cached delivery rate is $R^*(\gamma) = U(1-\gamma)$ — matching the trivial uncoded scheme. Demand privacy eliminates the MAN coded-multicast gain. Sharp negative result connecting PIR and coded caching.

• 4.

  Public vs. private side info: same capacity for uniformly-random caches; non-uniform private caches may incur a (small, open) rate cost. Cache content automatically private if placed long ago.

• 5.

  Open frontiers: joint extensions (coded + $T$-colluding + side info, etc.), non-uniform demand distributions (Zipf), adaptive protocols, wireless PIR, quantum PIR. Several remain unsettled even pairwise.