Exercises

$\Delta^*(\mu) = (1 - 0.4)/(25 \cdot 0.4) = 0.6 / 10 = 0.06$.

Uncoded: $1 - 1/25 = 0.96$. Gain: $0.96 / 0.06 = 16 = N\mu$.

(1) Identify the cut (subset of workers whose messages the master uses to decode).

(2) Apply the output-entropy bound: aggregate message entropy $\geq$ conditional output entropy given the other side.

(3) Symmetrize over all equivalent cuts (all subsets of the same size).

(4) Normalize by the output size to get the rate/load.

In step 2, the conditional entropy $H(Y \mid X_{\mathcal{S}^c})$ is reduced by the storage that the workers in $\mathcal{S}^c$ already hold — the reduction is governed by $\mu$.

$\Delta^*(1) = (1 - 1)/(N \cdot 1) = 0$.

At full replication every worker has the entire dataset, so no inter-worker communication is needed: each worker produces the full output independently and the master reads one copy. The cost is paid in per-worker storage equal to the full dataset.

$\Delta^*(0.2) = (1 - 0.2)/(20 \cdot 0.2) = 0.8/4 = 0.2$.

The claim $\Delta = 0.1$ violates the cut-set converse, which mandates $\Delta \geq 0.2$ at this $\mu$. Either the scheme is wrong, the scheme cheats by using more storage than $\mu = 0.2$, or the problem does not match the coded-shuffling setting of §2.3.

There are $\binom{N}{\mu N}$ subsets $\mathcal{T}$ of size $\mu N$ worth considering. For each subset, the members collaboratively serve the remaining $N - \mu N$ workers, broadcasting $\mu N$- wise XOR-combinations.

By a counting argument (see Li et al. 2018 §III.B), the total number of broadcast messages is $(N - \mu N) \binom{N}{\mu N + 1} / (\mu N + 1)$, and each message is a single chunk of the intermediate-value file.

Dividing by the intermediate-file size and simplifying gives $\Delta = (1 - \mu)/(N\mu)$, matching the theorem. (A fully worked combinatorial derivation is Exercise IV-2 in Li et al.'s paper; this exercise mainly tests understanding of the mechanism.)

At $\mu = 0.3$, the discrete points are $\mu = 0.2$ ($\Delta^* = 0.8/2 = 0.4$) and $\mu = 0.3$ directly ($\Delta^* = 0.7/3 \approx 0.233$). Since $\mu = 0.3$ is itself a discrete point, no interpolation is needed here.

Interpolate between $(0.2, 0.4)$ and $(0.3, 0.233)$. $\Delta(0.25) = (0.4 + 0.233)/2 = 0.317$. This is an upper bound on the smooth convex curve $(1-\mu)/(N\mu) = 0.3$ at $\mu = 0.25$.

$\Delta^*(\mu) = \frac{1}{N\mu} - \frac{1}{N}$.

$\Delta'(\mu) = -1/(N\mu^2)$; $\Delta''(\mu) = 2/(N\mu^3) > 0$ for $\mu \in (0, 1]$. Hence $\Delta^*$ is strictly convex.

Strict convexity means that memory-sharing between two discrete points gives a strictly higher communication load than the smooth curve — the discrete optimal is optimal only at its grid points.

The storage mappings are fixed protocols: worker $k$ always stores $\varphi_k(\mathcal{D})$, regardless of the realization. This ensures that the joint distribution of $(\mathcal{D}_1, \ldots, \mathcal{D}_N)$ is well-defined from the prior on $\mathcal{D}$ alone.

Cut-set bounds use conditional entropies like $H(Y \mid X_{\mathcal{S}^c})$, which require a well-defined joint distribution. If storage could depend on the input in an adaptive way, the analysis would have to track this adaptation — possible but complicating. Fortunately, all results in this book are proved under the fixed-mapping assumption and extend naturally when needed.

Define $\bar \mu = (1/N)\sum_k \mu_k$. A plausible generalization is $\Delta \geq (1-\bar\mu)/(N\bar\mu)$. Matching achievability requires a scheme that spreads load in proportion to the storage distribution — a non-trivial combinatorial problem.

Fixing a cut between some subset $\mathcal{S}$ and the master, the bound becomes $\sum_{k \in \mathcal{S}} H(X_k) \geq F(1 - \sum_{k \in \mathcal{S}^c} \mu_k)$, i.e., what can be reconstructed locally by the complement. Averaging over cuts weighted by the storage distribution gives the generalized converse — a good research-level exercise.

The result for non-symmetric storage is not fully characterized in general; partial results exist for special storage profiles. This is one of the open problems of Chapter 18.

The natural cut is between the server and the union of all users: all uplink traffic crosses this cut.

The server's output $\mathbf{G} = \sum_k \mathbf{g}_k \in \mathbb{R}^d$ has entropy $H(\mathbf{G}) \approx d \cdot b$ bits at $b$-bit precision.

Since each user must contribute information about its gradient, symmetry gives per-user uplink at least $H(\mathbf{g}_k) - H(\mathbf{g}_k \mid \mathbf{G})$, which for independent gradients is roughly $d \cdot b / n$ per user — but the aggregate is still $\Omega(n d b)$. This recovers the aggregation-cost theorem of Chapter 1 from the cut-set recipe.

Privacy against $T$ colluders is achieved by adding random masks that cancel in the aggregate. Each mask contributes to the communication load; the aggregate load rises to roughly $(1-\mu)/(N\mu) + T/N$, where the second term is the privacy overhead per-user.

Achievability uses ramp secret sharing (Chapter 3) and pairwise masking (Chapter 10). The exact tradeoff region is established in Caire et al.'s Optimality of Secure Aggregation with Uncoded Groupwise Keys paper, which we tag in Chapter 10. The conjecture here is qualitatively correct; the constants require the full construction.

The cut-set recipe transfers, but each additional adversary parameter adds its own structural term. This is the "Three challenges, one thread" principle made quantitative.

For asymmetric coded caching with unequal user memories, the cut-set bound can be improved via more delicate linear programming arguments (see Yu, Maddah-Ali, Avestimehr, 2017). The cut-set's gap to the true optimum is small in absolute terms but demonstrably non-zero.

Cut-set bounds assume the cut can be "fully" saturated with independent information. When multiple cuts share constraints (as in coded caching with asymmetric memories), the cut-set is not tight because it does not capture the joint constraints between cuts. Polyhedral methods (linear programming on entropy inequalities) give tighter bounds.

Characterizing when cut-set bounds are tight vs. loose is one of the persistent themes of multi-user information theory. For the vanilla coded-shuffling problem of this chapter, it happens to be tight; for richer settings it need not be.

Reed–Solomon decoding uses FFT-based polynomial interpolation with complexity $O(N \log^2 N)$ per symbol. For the canonical coded-shuffling scheme, the decoding is much simpler — each recipient performs one XOR per broadcast message — hence $O(\mu N)$ operations per chunk.

The coded-shuffling decoder is extremely cheap compared to general Reed–Solomon. This cost asymmetry (cheap decoding, moderate storage) is what makes coded shuffling practical even at the wireless edge. Polynomial codes for matrix multiplication (Chapter 5) have more expensive decoders but hit a stronger recovery threshold.

Over an AWGN MAC at high SNR, all $N$ users can transmit simultaneously and the receiver obtains $Y = \sum_k X_k + Z$ with $Z$ small. For an aggregation task the receiver's output is $\sum_k X_k$ itself, so the cost in "channel uses" is $\Theta(d)$ rather than $\Theta(N d)$ — a factor-$N$ saving over the bit-pipe baseline.

The $(\mu, \Delta)$ region on a wireless MAC can be strictly larger than on bit-pipes, because the channel itself performs aggregation. Chapter 16 makes this precise: the analog AirComp region sits above the digital region by a factor of $N$ in the high-SNR limit, at the cost of additional MSE.

$\Delta \;\geq\; \underbrace{\frac{1-\mu}{N\mu}}_{\text{structural}} \;+\; \underbrace{\frac{T}{N}}_{\text{privacy}} \;+\; \underbrace{\frac{2B}{N}}_{\text{Byzantine}}.$

The first term is the coded-shuffling converse of §2.4. The second is the privacy overhead from ramp secret sharing (Chapter 11). The third is the Byzantine-correction overhead from Reed–Solomon in the presence of $B$ adversarial errors.

The conjecture matches the achievability bounds of Chapters 10–12 and the ByzSecAgg CommIT contribution in Chapter 11, but a matching converse for the joint region is one of the open problems listed in Chapter 18. Interested readers are invited to formalize the decomposition and verify it against the existing constructions.

The exercise is a gentle invitation to treat the $(\mu, \Delta, T, B)$ framework as the design space for the remainder of the book. Every later chapter specializes to one slice of this 4-dimensional region; understanding the joint structure is what the book is about.