Chapter Summary

Chapter Summary

Key Points

• 1.

  Coded convolution achieves recovery threshold $K = p + q - 1$ — linear in the partitions. The entangled polynomial code exploits convolution's reduced output structure (only $p + q - 1$ distinct coefficients, not $pq$) to beat the standard polynomial code's $K = pq$ at the same per-worker storage.

• 2.

  Lagrange Coded Computing unifies the framework for arbitrary multivariate polynomials. Recovery threshold is $K_{\\text{rec}} = d_f(K - 1) + 1$ where $d_f$ is the function's total degree and $K$ is the number of input partitions. Polynomial codes, entangled polynomial codes, and gradient coding are all special cases.

• 3.

  Specialized schemes beat LCC for common operations. For matrix multiplication, polynomial codes achieve $K = pq$; LCC achieves $2pq - 1$. For convolution, entangled codes achieve $K = p + q - 1$; LCC achieves $2(p + q - 1) - 1$. Use specialized schemes when the operation is known; use LCC when generality is needed (higher-degree polynomials, unusual structures).

• 4.

  The non-polynomial barrier is the current frontier. Coded computing handles polynomial operations optimally but cannot exactly compute non-polynomial functions (ReLU, softmax, exponentials, cross-entropy). Workarounds include polynomial approximation, hybrid coding (polynomial layers coded, non-polynomial replicated), and cryptographic MPC for non-polynomial operations.

• 5.

  Part II closes with a mature framework for polynomial distributed ML. Polynomial codes (Ch. 5), gradient coding (Ch. 6), coded shuffling (Ch. 7), entangled / Lagrange coded computing (Ch. 8). Each class of polynomial computation has an optimal scheme with matching achievability and converse. Production adoption is limited; research continues on the non-polynomial frontier and on composition with privacy / Byzantine primitives.