Exercises

Standard polynomial code: $K = pq = 15$. Entangled polynomial code: $K = p + q - 1 = 7$. A $2\times$ reduction in recovery threshold at the same storage.

$d_f = 2$ (quadratic in each variable, but each term involves only one variable). Number of inputs $K = 6$.

$K_{\text{rec}} = d_f(K - 1) + 1 = 2 \cdot 5 + 1 = 11$.

ReLU is piecewise-linear but not polynomial; it cannot be expressed as a finite-degree polynomial on $\mathbb{R}$. LCC requires $f$ to be polynomial.

(i) Approximate ReLU by a low-degree polynomial, apply LCC with bounded error; (ii) use cryptographic MPC (garbled circuits) for the ReLU step separately; (iii) replicate the ReLU layer across workers (hybrid coding).

$K_{\text{rec}} = 2 \cdot 4 + 1 = 9$.

$K_{\text{rec}} = 3 \cdot 4 + 1 = 13$.

Cubic requires $13/9 \approx 1.44\times$ more responses. Linear scaling with function degree.

$p_{\mathbf{a}}(x) = \mathbf{a}_1 + x \mathbf{a}_2 + x^2 \mathbf{a}_3$ (degree 2). $p_{\mathbf{b}}(x) = \mathbf{b}_1 + x \mathbf{b}_2 + x^2 \mathbf{b}_3 + x^3 \mathbf{b}_4$ (degree 3).

$p_{\mathbf{c}}(x) = p_{\mathbf{a}}(x) p_{\mathbf{b}}(x)$ has degree 5, so $p + q - 1 = 6$ evaluations suffice.

$K = 6$.

LCC treats the target as a generic polynomial of degree $d_f$. Specialized codes exploit operation-specific algebraic structure (e.g., convolution's sparse monomial basis) to reduce the effective degree.

Higher-degree operations (quartic or quintic polynomial activations in privacy-preserving neural networks), arbitrary multi-tensor contractions, or federated computation of higher-order statistics (skewness, kurtosis).

Use specialized codes per-operation type; use LCC only for operations without specialized schemes. Production frameworks dispatch on operation type.

$u(z)$ has degree $K - 1$ as a polynomial in $z$. $f(u(z))$ applies $f$ (degree $d_f$) to $u(z)$; the degree of the composition is $d_f \cdot \deg u = d_f(K - 1)$.

Any polynomial of degree $\leq d_f(K - 1)$ is uniquely determined by $d_f(K - 1) + 1$ distinct evaluations. Hence $K_{\text{rec}} = d_f(K - 1) + 1$.

$K = pq = 16$ at storage $\mu = 1/p + 1/q = 1/2$. Optimal at this storage.

$K = p + q - 1 = 7$ at higher storage $\mu' = 1/\min(p, q) = 1/4$. Better threshold, but more storage per worker.

$K_{\text{rec}} = d_f(K - 1) + 1 = 2 \cdot 15 + 1 = 31$. Worse than the standard polynomial code — LCC is not the right tool for this structured operation.

For $(p = q = 4)$ matmul at $\mu = 1/2$ storage, use the standard polynomial code. MatDot buys a smaller threshold at the cost of more storage. LCC is not the right tool here.

$\hat\sigma_5(x) \approx 0.5 + 0.2159 x - 0.0083 x^3 + 0.000119 x^5$.

Max error on $[-5, 5]$: $\approx 0.01$ (1% of output range). Higher-degree approximations reduce error at cost of LCC recovery-threshold overhead.

With degree 5, $K_{\text{rec}}^{\text{LCC}} = 5(K - 1) + 1$. For $K = 10$ inputs, that's $46$ responses — a substantial overhead. Use this only when exact sigmoid is critical and polynomial-approximation error is acceptable.

Privacy-preserving logistic regression, where the sigmoid appears once per prediction and polynomial approximation (degree 3–5) is standard practice.

Each tensor gets a polynomial encoding with exponents $i, j, s$ for $A$ and $s, k, \ell$ for $B$. The product polynomial has degree equal to the sum of the polynomial degrees, minus one for the contracted index.

The total degree of the product polynomial, treated as a single-variable polynomial (by interleaving exponents), gives $K = p_1 + p_2 + p_3 + p_4 - 3$.

Yu et al. (2020) give the precise construction for 3-tensor contractions; 4-way contractions follow the same pattern.

The polynomial $f(u(z))$ has degree $d_f(K - 1)$. Its coefficient vector has $d_f(K - 1) + 1$ independent entries. Any scheme recovering this polynomial requires at least that many independent worker responses.

The target $f(\mathbf{x}_1, \ldots, \mathbf{x}_K)$ is one evaluation of this polynomial; recovering it generically requires recovering the whole polynomial. Hence $K_{\text{rec}} \geq d_f(K - 1) + 1$.

The LCC construction matches this bound with equality via Lagrange interpolation on the $N$ worker evaluations. The full proof is in Yu et al. 2019 Thm. 1. $\blacksquare$

Extend the Lagrange polynomial $u(z)$ to include $T$ additional random terms: $u_{\text{priv}}(z) = \sum_{j=1}^K \mathbf{x}_j \ell_j(z) + \sum_{\ell=1}^T \mathbf{r}_\ell \beta_{K+\ell}(z)$, where $\mathbf{r}_\ell$ are uniform random vectors and $\beta_{K+\ell}$ are Lagrange bases on additional "masking" points.

$u_{\text{priv}}(z)$ has degree $K + T - 1$. $g_{\text{priv}}(z) = f(u_{\text{priv}}(z))$ has degree $d_f(K + T - 1)$.

$K_{\text{rec}}^{\text{priv}} = d_f(K + T - 1) + 1$. Cost: $d_f \cdot T$ extra responses for $T$-privacy.

Privacy cost scales linearly in $T$ and in $d_f$. For high-degree functions, privacy is especially expensive. Soleymani et al. 2021 formalize this result.

Degree-$d$ Chebyshev approximation of a smooth non-polynomial $f$ has max error decaying exponentially in $d$. For deep networks with $L$ layers, accumulated error scales as $L \cdot \epsilon$ (if $\epsilon$ is per-layer error).

Per-layer LCC threshold: $d \cdot (K - 1) + 1$. Deep network with $L$ layers: effective degree is $d^L$ (composition), so overall LCC threshold becomes $d^L (K - 1) + 1$ — exponential in the depth!

Per-layer coding (one LCC instance per layer) avoids the degree-explosion; overall overhead is $L$-times per-layer. Much more practical.

Choose $d$ by per-layer error budget and per-layer LCC overhead. For $L = 100$ layers, degree $d = 5$, the per-layer threshold overhead is modest but accumulated error may be unacceptable. Research direction: end-to-end analysis of polynomial- approximate deep learning.

Forward: convolution → activation → ... → loss. Backward: loss → derivative-of-activation → transposed-convolution → ... Each convolution is codable via entangled polynomial codes ($K = p + q - 1$). Each activation is non-polynomial (replicated or approximated).

The per-layer gradient $\partial L/\partial \mathbf{W}$ aggregates over mini-batches. Gradient coding (§6.2) applies to the aggregation; the per-layer convolutions apply independently.

For a $(p = q = 8)$-convolution with $s = 2$-straggler gradient aggregation: $K_{\text{conv}} = 15$, $K_{\text{grad}} = N - 2$. The overall per-layer operation waits for $\max(K_{\text{conv}}, K_{\text{grad}})$ — typically gradient-coding limits are more relaxed, so $K_{\text{conv}}$ dominates.

Optimizing jointly across layers (re-balancing partition counts per layer to minimize end-to-end latency) is an active research problem.

Define: input dimension $d$, function $f$ with Lipschitz constant $L$, approximation tolerance $\epsilon$, number of workers $N$. Goal: achieve $\|\widehat{f(\mathbf{x})} - f(\mathbf{x})\|^2 \leq \epsilon^2$ at minimum $K_{\text{rec}}$.

Define a "coded rate" $R = K_{\text{rec}} / N$. The optimal rate as a function of $\epsilon$ and $L$ is $R^*(\epsilon, L) = \text{(some function of } L, \epsilon, d\text{)}$. For polynomial $f$, $R^*(0, L) = d_f/N$ (exact LCC). For non-polynomial with Lipschitz $L$, the rate-distortion curve is an open characterization.

Jahani-Nezhad & Maddah-Ali 2022 (Berrut Approximated Coded Computing) give partial answers using rational-function approximations. The optimal rate-distortion curve is a research frontier.

This is one of the open problems of Chapter 18. Interested researchers should combine rate-distortion theory with coded-computing IA, explicit construction, and convergence analysis.