Part IV Summary and the Frontier

Part IV in Perspective

Part IV (Chapters 13-15) developed the information-theoretic theory of Private Information Retrieval. The arc:

Chapter 13: classical PIR. Sun-Jafar capacity $C(N, K) = (\sum_{i=0}^{K-1} N^{-i})^{-1}$ .
Chapter 14: extensions. Coded storage (Tajeddine-El Rouayheb), $T$ -colluding databases (Sun-Jafar 2018), symmetric PIR (Sun-Jafar 2018c).
Chapter 15: side information and caches. Wei-Banawan-Ulukus 2019 for single-user side info; Wan-Tuninetti- Caire 2021 for multi-user cached delivery with demand privacy (CommIT contribution).

The unifying themes — capacity formulas via geometric series, cut-set converses, finite-field IA achievability — connect PIR to the rest of this book. Section §15.4 closes Part IV by summarizing the landscape and pointing to the open frontier.

Part IV — All PIR Variants

Variant	Constraint	Capacity	Reference	Status
Classical PIR	$N$ DBs, replicated, no collusion	$(1 + 1/N + \cdots + 1/N^{K-1})^{-1}$	Sun-Jafar 2017	Settled
Coded-storage PIR	$(N, r)$ -MDS storage	$(1 + r/N + \cdots + r^{K-1}/N^{K-1})^{-1}$	Tajeddine 2018	Settled
$T$ -colluding PIR	$T$ -collusion privacy	$(1 + T/N + \cdots + T^{K-1}/N^{K-1})^{-1}$	Sun-Jafar 2018	Settled
SPIR	Two-sided privacy	$1 - 1/N$	Sun-Jafar 2018c	Settled
SPIR + coded	Two-sided + MDS	$1 - r/N$	Wang-Skoglund 2019	Settled
Coded + $T$ -colluding	MDS + collusion	Achievable known	Freij-Hollanti 2018	Open in general $K$
PIR with side info	$M$ uncoded prefetched files	$(1 + 1/N + \cdots + 1/N^{K-M-1})^{-1}$	Wei-Banawan-Ulukus 2019	Settled
Cache-aided PIR (uncoded)	$\gamma K L$ random uncoded cache	Binomial mixture of $C(N, K-i)$	Wei-Banawan-Ulukus 2019	Settled
Multi-user demand-private (CommIT)	$U$ users, cache, demand privacy	$U(1 - \gamma)$	Wan-Tuninetti-Caire 2021	Settled (uniform demands)

The Open Frontier

The open problems in PIR fall into several categories:

Joint extensions: combining coded storage, $T$ -colluding, SPIR, side info in pairs or triples. Most pairwise combinations are open in general $K$ .
Non-uniform regimes: most capacity results assume uniform random demands and uniform cache contents. Skewed (e.g., Zipf) distributions yield lower-rate constraints with open characterizations.
Adaptive PIR: when the user can adapt queries based on previous answers. Open whether the rate improves over the non-adaptive case.
Latency-amortized rate: the capacity is defined for one-shot retrieval. Latency-amortized rate (over a sequence of queries) has different characteristics, not yet fully characterized.
Wireless PIR: PIR over wireless channels — combining the channel capacity with the PIR capacity. Most known results assume noiseless broadcast; wireless extensions are active research.
Quantum PIR: PIR with quantum databases or quantum communication. Sun-Jafar-style capacity results have been extended to the quantum regime; open questions about the quantum-classical gap remain.

The CommIT group's research program addresses several of these frontiers, notably (1), (2), and (5). Chapters 16-17 begin the wireless extensions.

PIR in the Larger Distributed-Computing Story

PIR is structurally a distributed computing problem: the user "computes" the desired file via a query-answer protocol. The capacity results in Part IV use the same information-theoretic toolkit as Parts I–III:

Cut-set converses (Chapter 2).
Finite-field IA (Chapter 4) — the achievability backbone of every Sun-Jafar-style scheme.
Secret-sharing primitives (Chapter 3) — Shamir for $T$ -colluding, MDS for coded storage.

In this sense, Part IV is not a separate topic but a specialization of the coded-computing framework: the "function" being computed is "select file $\theta$ ," and the "encoding" is the PIR query structure.

The framework will continue evolving in Part V (Chapters 16-18): wireless extensions, federated learning, and open frontiers. PIR has emerged in $\sim 8$ years (Sun-Jafar 2017 → present) from a $\sim 22$ - year-old open problem (Chor 1995) to a rich, well-developed theory. The current open problems (above) are the next 8 years of research.

Why This Matters: Looking Ahead: Wireless and AirComp

Part V of this book (Chapters 16-18) shifts to wireless settings. Chapter 16 introduces AirComp (over-the-air computation), Chapter 17 covers wireless federated learning, and Chapter 18 outlines open problems and frontiers.

The PIR framework can be extended to wireless channels — the user broadcasts queries; databases respond simultaneously over a multiple-access channel. Channel noise and interference change the capacity calculation but not the structural privacy requirement. Chapter 16 discusses AirComp variants that incorporate privacy, connecting Part IV's framework to wireless physical- layer constraints.

Chapter 17 carries the fifth CommIT contribution: information-theoretically secure federated representation learning over wireless channels. The book closes with Chapter 18's open-problems discussion.

Key Takeaway

Part IV closes with PIR variants spanning the storage-privacy-rate Pareto frontier. The CommIT contribution (Wan-Tuninetti-Caire 2021) settled the multi-user demand-private cached delivery case. Open frontiers include joint extensions, non-uniform demand distributions, adaptive protocols, and wireless variants — addressed in part by Part V.

Common Mistake: Capacity Is the Best Possible Rate, Not the Achievable Rate

Mistake:

Confuse the PIR capacity (Sun-Jafar's formula) with the rate of a specific scheme (which may be lower).

Correction:

The PIR capacity $C_{\text{PIR}}(N, K)$ is the supremum of achievable rates over all PIR schemes. A specific implementation may achieve less (e.g., a practical scheme with finite block length, non-asymptotic overhead, or sub-optimal encoding). When deploying PIR, benchmark the implemented rate, not the asymptotic capacity. The capacity is a useful target; the implementation gap can be substantial in finite-block-length regimes.

Quick Check

Which of the following statements about Part IV (PIR) is true?

Most pairwise combinations of PIR extensions are settled in capacity.

The CommIT contribution (Wan-Tuninetti- Caire 2021) addresses multi-user cached delivery with demand privacy.

PIR capacity always equals $1$ (perfect recovery).

Wireless PIR is fully characterized.

Correction:

The CommIT contribution (Wan-Tuninetti- Caire 2021) addresses multi-user cached delivery with demand privacy.

Correct. WTC 2021 shows that demand privacy in multi-user cached delivery eliminates the coded-multicast gain of MAN.

Cached Delivery with Demand Privacy Chapter Summary