Exercises

$\mathbf{U}_k \mathbf{H}_{kj} \mathbf{V}_j = \mathbf{0}$ for every $j \neq k$, while $\mathbf{U}_k \mathbf{H}_{kk} \mathbf{V}_k$ has full column rank.

All $K - 1$ unintended transmissions at each receiver align into a common $(N/2)$-dimensional subspace (the nullspace of $\mathbf{U}_k$), freeing the other half of the signal space for the intended message.

$K = pq = 15$.

Full replication would have $\mu = 1$ and $K = 1$ (one worker's response suffices). At $\mu = 1/p + 1/q = 1/5 + 1/3 = 8/15$, polynomial codes achieve $K = 15$ — better straggler tolerance at lower storage.

$1 + KM/F = 1 + 8 \cdot 4/16 = 3$. Coded caching is $3\times$ more efficient than uncoded.

$R^* = K(1 - M/F)/(1 + KM/F) = 8 \cdot (3/4)/3 = 2$.

$C_{\text{PIR}} = (1 + 1/5 + 1/25 + 1/125)^{-1} = (1 + 0.2 + 0.04 + 0.008)^{-1} = 1/1.248 \approx 0.801$.

For every bit of downloaded data from the 5 databases, the user receives about $0.80$ bits of useful file content — nearly the theoretical maximum of $1 - 1/N = 0.80$.

With uniform per-user DoF $d$, each receiver must null $K - 1 = 2$ interferers of dimension $d$ each, requiring $N \geq (K-1) d + d = Kd$, i.e., $d \leq N/K = 2$.

$d \approx N/2 = 3$ per user in the limit. At finite $N = 6$ one gets $d = 2$ or $3$ depending on rounding.

IA gains a factor of $K/2$ over zero-forcing in the sum-DoF: $2 \cdot (3/2) = 3$ vs. $2 \cdot 1 = 2$. At $N = 6$, the practical gain is about $1.5\times$.

Worker $k$ stores $\tilde{\mathbf{A}}_k = \mathbf{A}_1 + \alpha_k \mathbf{A}_2$ and $\tilde{\mathbf{B}}_k = \mathbf{B}_1 + \alpha_k^2 \mathbf{B}_2$, for $\alpha_k = k$ mod 7.

$\tilde{\mathbf{C}}_k = p(\alpha_k)$ where $p(x) = \mathbf{C}_{11} + x \mathbf{C}_{21} + x^2 \mathbf{C}_{12} + x^3 \mathbf{C}_{22}$, degree 3.

$K = pq = 4$. Master can tolerate $N - K = 1$ straggler.

Collect any $4$ responses and interpolate the degree-3 polynomial via Lagrange interpolation; the four coefficients are the four output blocks.

For demand $\mathbf{d}$ with all-distinct files, the $K$ users collectively need $K$ files' worth of information. They already cache $KM/F$ files' worth; the server broadcast must supply the remaining $K(1 - M/F)/(1 + KM/F)$ files — exactly the Maddah-Ali / Niesen rate.

The global gain $1 + KM/F$ cannot be exceeded because every broadcast can satisfy at most $1 + KM/F$ users simultaneously (each bit of the broadcast lies in at most $1 + KM/F$ user "cache-aligned" subspaces).

The converse is strictly for centralized placement; decentralized placement has a slightly relaxed converse (see Maddah-Ali / Niesen §VI).

$W_1 = (W_{1,1}, W_{1,2}, W_{1,3})$, $W_2 = (W_{2,1}, W_{2,2}, W_{2,3})$.

• DB 1: returns $W_{1,1}$.
• DB 2: returns $W_{1,2}$.
• DB 3: returns $W_{1,3} \oplus W_{2,1}$.
• Need additionally $W_{2,1}$ for cancellation; DB 3 also returns $W_{2,1}$.

Total: 4 chunks downloaded. Rate $= 3/4$. ✓

Each database sees one or two chunk-labels of each file; the choice of which labels depends on a random permutation unknown to any single database. With the permutation uniform, each database's query is statistically independent of the desired index $\theta$.

Any $pq \times pq$ submatrix of a Vandermonde matrix (with distinct evaluation points) is invertible. Zero failure probability.

With i.i.d. uniform coefficients in $\mathbb{F}_q$, a $pq \times pq$ submatrix is singular with probability $\leq pq/q$. For $q < pq^2$ this failure probability exceeds $1/pq$ — noticeable.

Production systems use polynomial codes, not random encoding. The wireless-IA literature fascination with generic randomized constructions does not carry over to the algebraic, code-based distributed computing setting.

Let $\mathbf{H}_{11} = \mathbf{I}$, $\mathbf{H}_{22} = \mathbf{I}$, $\mathbf{H}_{12} = \mathbf{H}_{21} = \text{diag}(1, 2, 3, 4)$ over $\mathbb{F}_7$.

$\mathbf{V}_1 = [\mathbf{e}_1, \mathbf{e}_2]$, $\mathbf{V}_2 = [\mathbf{e}_3, \mathbf{e}_4]$. The interferer at receiver 1 is $\mathbf{H}_{12} \mathbf{V}_2 = \text{diag}(1,2,3,4) \cdot [\mathbf{e}_3, \mathbf{e}_4] = [3\mathbf{e}_3, 4\mathbf{e}_4]$. Choose $\mathbf{U}_1 = [\mathbf{e}_1, \mathbf{e}_2]^\top$ — null of the interferer.

$\mathbf{U}_1 \mathbf{H}_{12} \mathbf{V}_2 = [\mathbf{e}_1, \mathbf{e}_2]^\top [3\mathbf{e}_3, 4\mathbf{e}_4] = \mathbf{0}$ ✓. $\mathbf{U}_1 \mathbf{H}_{11} \mathbf{V}_1 = \mathbf{I}_2$, full rank ✓. Similarly at receiver 2. Per-user DoF: $d = 2$. Sum DoF: $4 = N$, matching the no-interference upper bound.

Within uncoded placement (each user caches file chunks in plain), the MN scheme achieves the cut-set bound $1 + KM/F$ exactly (see Yu/Maddah-Ali/Avestimehr 2018). Any scheme reaching this bound is optimal.

Yu / Maddah-Ali / Avestimehr (2018) showed a marginal improvement with coded placement for small $K$. The gap vanishes as $K \to \infty$, so asymptotically the MN bound is tight. At $K \leq 4$ the coded- placement rate can be up to $\sim 12\%$ smaller.

For the production regimes of interest ($K \geq 10$), the MN bound is tight and coded placement offers negligible advantage. Uncoded placement is therefore the right default in Chapter 7's shuffling analysis.

Replace the polynomial-code polynomial $p(x) = \sum_{i,j} \mathbf{C}_{ij} x^{i + pj}$ by a randomized version $p(x) = \sum_{i,j} \mathbf{C}_{ij} x^{i + pj} + \sum_{\ell = 0}^{T-1} \mathbf{Z}_\ell x^{pq + \ell}$, where $\mathbf{Z}_\ell$ are fresh random matrices.

$K = pq + T$. The added $T$ terms preserve privacy (any $T$ evaluations are uniform random) at the cost of $T$ more worker responses for the master to decode.

The privacy parameter $T$ adds linearly to the recovery threshold. For $T = 1$, one extra worker in exchange for perfect secrecy against any single worker. This is the construction used in Chapter 11 for ByzSecAgg.

As $F \to \infty$, $1/N^F \to 0$, so $C_{\text{PIR}} \to (1 - 1/N)/1 = 1 - 1/N$.

With a huge library, the PIR download rate per byte of useful content is $1/(1 - 1/N) = N/(N-1)$. With 2 databases this is $2$; with 5 databases, $1.25$. More databases $\implies$ less overhead — the marginal cost of privacy vanishes as the system scales.

Practical PIR deployments care about finite-$F$ behavior, where the capacity formula has a small correction. Chapter 13 develops the coded-storage variant where the effective file size grows and the correction becomes visible.

Both constructions express a target computation (matrix product; file retrieval) as a polynomial evaluation, and decode via Lagrange interpolation on a subset of evaluations. Both achieve optimality from finite-field IA: cross-channel alignments reduce to Vandermonde invertibility.

Coded matrix multiplication aligns many output blocks (the $pq$ entries of the product) into a low-degree polynomial; PIR aligns file interferers (the $F - 1$ non-requested files) into a small number of independent directions. The first is a source-coding-style counting argument; the second is a privacy-preserving download.

Both problems are instances of finite-field IA in the "many-to-one" configuration — many messages, one receiver (master or user). The alignment reduces the effective per-unit overhead from $\Theta(K)$ (trivial) to $\Theta(1)$ (IA-optimal) — exactly the DoF gain of Section 4.1 in another disguise.

For a single product, polynomial codes give $K = pq$ (§4.2). For a stream of products, cached intermediate values (the $\mathbf{A}^{(k)} \mathbf{B}^{(k)}$ sub-products or their polynomial combinations) can be reused across products.

The effective recovery threshold for a stream of products with cache size $M$ scales as $K_{\text{eff}} = pq / (1 + KM/F)$ in the many-products limit — achieving a $1 + KM/F$ reduction in the per-product straggler-tolerance requirement. The total per-worker storage is $\mu + M$.

The precise tradeoff is open. The CCG (coded-computing with caching) literature (2019–present) has partial achievability results but no matching converse. This is a genuine open problem at the intersection of coded computing and coded caching — a natural research direction extending the IA machinery of this chapter.