Exercises

$\mu = 1/4 + 1/5 = 9/20$; $K = pq = 20$; $\deg p_C = pq - 1 = 19$.

$K = pq = 16$. Straggler tolerance $= N - K = 30 - 16 = 14$ — almost half of all workers can fail.

$\mathbb{F}_q$ has $q - 1$ nonzero elements. The polynomial code needs $N$ distinct nonzero $\alpha_k$, so $q - 1 \geq N$, i.e., $q \geq N + 1$. Practically we round up to a prime power $\geq N + 1$.

Polynomial: $K = 16$. MDS: $K = 7$. MDS has lower $K$ but higher per-worker storage ($\mu = 1/\min(p, q) = 1/4$ for MDS vs. $1/p + 1/q = 1/2$ for polynomial). Different tradeoffs.

$\tilde{\mathbf{A}}_5 = \mathbf{A}_1 + 5 \mathbf{A}_2$; $\tilde{\mathbf{B}}_5 = \mathbf{B}_1 + 25 \mathbf{B}_2 + 625 \mathbf{B}_3 \equiv \mathbf{B}_1 + 3 \mathbf{B}_2 + 9 \mathbf{B}_3 \pmod{11}$.

$\tilde{\mathbf{C}}_5 = \tilde{\mathbf{A}}_5^T \tilde{\mathbf{B}}_5 = p_C(5)$ where $p_C$ has degree $pq - 1 = 5$.

$K = 6$. Master can tolerate $N - K = 2$ stragglers.

$p_C(x) = (\sum_{i=0}^{p-1} \mathbf{A}_{i+1} x^i)^T (\sum_{j=0}^{q-1} \mathbf{B}_{j+1} x^{pj}) = \sum_{i, j} \mathbf{A}_{i+1}^T \mathbf{B}_{j+1} x^{i + pj} = \sum_{i, j} \mathbf{C}_{i+1, j+1} x^{i + pj}$.

The exponents $i + pj$ for $(i, j) \in [p] \times [q]$ are distinct (since $i \in \{0, \ldots, p-1\}$ uniquely encodes the residue mod $p$). Hence each $\mathbf{C}_{ij}$ appears as a distinct coefficient, and Lagrange interpolation recovers all of them independently.

Responders: $\{1, 2, 4, 5, 6, 8, 9, 10, 11\}$ — exactly $9$ workers. The master does not need to know which workers will straggle in advance.

With distinct evaluation points $\alpha_1, \alpha_2, \alpha_4, \alpha_5, \alpha_6, \alpha_8, \alpha_9, \alpha_{10}, \alpha_{11}$, Lagrange interpolation succeeds because any $9 \times 9$ Vandermonde submatrix is invertible.

The full output $\mathbf{A}^T \mathbf{B}$ is recovered exactly. The straggler tolerance $N - K = 3$ is exactly the number of failed workers — at the edge of the budget.

For each output coefficient, compute Lagrange basis $\ell_k(\lambda)$ in $O(K)$ time. Sum over $k$ for $K$ coefficients: $O(K^2)$ total.

Using the polynomial-evaluation FFT and inverse-FFT algorithms, polynomial interpolation runs in $O(K \log^2 K)$ provided the field has a primitive $K$-th root of unity. For $K = 1024$, this is roughly a $30\times$ speedup over naive Lagrange.

The FFT speedup is significant for $K \geq 64$ or so. Below that, the naive approach is simpler and the constant factors of FFT overhead dominate. Modern coded-computing libraries provide both algorithms and switch based on $K$.

$\mu_{\text{MDS}} = 1/\min(p, q) = 1/4$. Each worker stores $1/4$ of $\mathbf{A}$ and $1/4$ of $\mathbf{B}$ — total $1/2$ of each input.

$\mu_{\text{poly}} = 1/p + 1/q = 1/4 + 1/4 = 1/2$. Same per-worker storage as MDS in this case.

At $p = q$, the storage budgets are identical. The difference is the recovery threshold: MDS achieves $K = p + q - 1 = 7$ vs. polynomial's $K = pq = 16$. MDS is better for straggler tolerance at this storage. The catch is that MDS requires a different polynomial structure that is sensitive to the partition shape; polynomial codes generalize more cleanly to $p \neq q$.

$K = pq = 64$.

$\mathbb{E}[T_{(K)}] = (H_N - H_{N-K})/\lambda = (H_{80} - H_{16})/1$. Compute: $H_{80} \approx 4.965$, $H_{16} \approx 3.381$. $\mathbb{E}[T_{(K)}] \approx 1.584$.

With $K = N = 80$ (no redundancy), $\mathbb{E}[T_{(N)}] = H_{80} \approx 4.965$ — about $3.1\times$ slower. The polynomial-code redundancy buys a factor-3 speedup at this $(N, K)$ point.

For any $\mathcal{U} \subset [N]$ with $|\mathcal{U}| \leq T$, $I(\mathbf{A}, \mathbf{B}; \{\tilde{\mathbf{A}}_k, \tilde{\mathbf{B}}_k\}_{k \in \mathcal{U}}) = 0$.

Coalition's view of $p_A$: $T$ evaluations $\{p_A(\alpha_k)\}_{k \in \mathcal{U}}$. The polynomial $p_A$ has $p$ "data" coefficients $\mathbf{A}_1, \ldots, \mathbf{A}_p$ plus $T$ random $\mathbf{Z}_{A, \ell}$. The Vandermonde linear system $\{p_A(\alpha_k) = \cdots\}_{k \in \mathcal{U}}$ has $T$ random degrees of freedom on the right-hand side, fully absorbing the $T$ observations. Hence the observations are uniform over the masking space, independent of $\mathbf{A}$.

Identical: the $T$ random terms in $p_B$ absorb the $T$ observations. By symmetry, no information about $\mathbf{B}$ leaks.

Since the masks for $p_A$ and $p_B$ are drawn independently, joint independence follows directly. $\blacksquare$

$p_A(x) = \sum_{i=0}^{p-1} \mathbf{A}_{i+1} x^i + \sum_{\ell=p}^{p+T-1} \mathbf{Z}_{A, \ell} x^\ell$, $p_x(x) = \mathbf{x}$ (no partitioning since $\mathbf{x}$ is a vector). Worker $k$ computes $\tilde{\mathbf{y}}_k = p_A(\alpha_k) \mathbf{x} = p_y(\alpha_k)$ where $p_y$ has degree $p + T - 1$.

$K = p + T$. With $T = 0$ this matches the polynomial- code $K = pq = p$ (since $q = 1$), and each privacy unit costs $1$ extra response (vs. $2$ in the matrix- matrix case because $p_x$ does not need its own masking).

Per-worker storage $= |\mathbf{A}|/p + |\mathbf{x}|/1 = 1/p + 1$ (in normalized terms — vector is small relative to matrix). Privacy adds $T/p$ to the storage.

The §5.3 converse applies to schemes where $\tilde{\mathbf{A}}_k$ and $\tilde{\mathbf{B}}_k$ are independent linear combinations of $\mathbf{A}_i, \mathbf{B}_j$. MatDot introduces entanglement — the encoding of $\mathbf{B}_j$ depends on properties of $\mathbf{A}$ as well, breaking the independence assumption.

The converse holds for "separable" coded schemes (each worker stores a separable function of the inputs). MatDot uses a joint encoding that does not fit this template.

Information-theoretic lower bounds depend on the scheme class. Tight bounds for one class can be beaten by extending to a strictly larger class. The coded-computing literature has many such "partial converse" results, and characterizing the full achievable region remains an active research area.

Replace $\alpha_k = k$ with Chebyshev nodes $\alpha_k = \cos((2k - 1)\pi / (2K))$. Condition number drops to $\sim 2^K \approx 10^{30}$ — still large but tractable in 128-bit floats.

Compute the matrix product modulo a large prime (e.g., $q = 2^{61} - 1$), then lift back to reals. Avoids floating-point conditioning entirely. Cost: modular reduction of large matrices.

Replace the Vandermonde encoding with a random orthogonal matrix $\mathbf{Q}$. Provides recovery threshold $K = pq$ with condition number $\sim 1$ (orthonormal rows). Cost: random encoding loses the explicit Lagrange decoder structure.

Most production deployments use Strategy 2 (finite- field arithmetic), often with $q$ chosen to match the natural data type (e.g., $\mathbb{F}_{2^{32}}$ for int32 matrices). Strategy 1 is the right choice when finite-field arithmetic is too slow.

Assign each worker a budget $b_k$ (number of evaluation points it can store). Encode $\mathbf{A}, \mathbf{B}$ as polynomials with degrees adapted to the per-worker budgets — workers with more budget store more coefficients. The recovery threshold becomes the smallest $K$ such that $\sum_{k \in \mathcal{T}} b_k \geq pq$ for any $K$-subset $\mathcal{T}$.

For storage budgets $\mu_1 \geq \mu_2 \geq \cdots \geq \mu_N$, the optimal $K$ is the smallest integer such that $\sum_{k = 1}^K \mu_k \geq 1/p + 1/q$ (i.e., the $K$ workers with the smallest budgets collectively store enough). This is similar to the "fractional cover" formulation in coded caching.

The conjecture is consistent with known special cases (symmetric storage recovers $K = pq$). A matching converse is open. This is one of the open problems of Chapter 18 — a research direction at the intersection of coded computing and combinatorial optimization.