Ferkans — Interactive Telecom Tutor

One Framework for All Polynomial Computations

Sections 8.1–8.2 gave specialized codes for matrix multiplication and convolution. What about general tensor contractions? Polynomial evaluations on arbitrary structured inputs? Higher-order multilinear operations?

The answer is Lagrange Coded Computing (LCC), introduced by Yu, Raviv, Soleymani, and Avestimehr (2019). LCC provides a single framework that achieves information-theoretically optimal recovery thresholds for arbitrary multivariate-polynomial functions — polynomial codes and entangled polynomial codes are both special cases.

The point is that LCC unifies the coded-computing toolbox: one encoding scheme (Lagrange interpolation over polynomial-valued inputs), one decoding algorithm (Lagrange interpolation), one recovery-threshold formula. Section 8.3 gives the framework; §8.4 discusses its limitations and open research directions.

Definition:
Lagrange Coded Computing (LCC)

Let $f: (\mathbb{F}_q^d)^K \to \mathbb{F}_q^{d'}$ be a multivariate polynomial function of $K$ vector inputs, of total degree $d_f$ . The goal: given inputs $\mathbf{x}_1, \ldots, \mathbf{x}_K \in \mathbb{F}_q^d$ , compute $f(\mathbf{x}_1, \ldots, \mathbf{x}_K)$ using $N \geq K$ distributed workers.

LCC construction. Pick distinct interpolation points $\beta_1, \ldots, \beta_K \in \mathbb{F}_q$ (one per input). Define the Lagrange polynomial $u(z) \;\triangleq\; \sum_{j = 1}^{K} \mathbf{x}_j \cdot \ell_j(z),$ where $\ell_j(z) = \prod_{i \neq j} (z - \beta_i)/(\beta_j - \beta_i)$ are the Lagrange basis polynomials with the property $\ell_j(\beta_i) = \delta_{ij}$ . Each worker $k$ is assigned an evaluation point $\alpha_k \in \mathbb{F}_q \setminus \{\beta_1, \ldots, \beta_K\}$ and stores $\tilde{\mathbf{x}}_k = u(\alpha_k)$ .

Worker computation. Worker $k$ computes $\tilde{y}_k = f(\tilde{\mathbf{x}}_k)$ , a single evaluation of $f$ . By construction, $\tilde{y}_k = f(u(\alpha_k)) = g(\alpha_k)$ where $g(z) \triangleq f(u(z))$ is a polynomial in $z$ of degree $d_f \cdot (K - 1)$ .

Master decoding. The master receives any $K_{\text{rec}} = d_f (K - 1) + 1$ worker responses and Lagrange-interpolates $g(z)$ . Evaluating at the interpolation points $\beta_j$ gives $g(\beta_j) = f(u(\beta_j)) = f(\mathbf{x}_j)$ — wait, this isn't quite right. Properly: if all inputs are provided as $\mathbf{x}_j$ for $j = 1, \ldots, K$ , then the target is $f(\mathbf{x}_1, \ldots, \mathbf{x}_K)$ , not $K$ separate function evaluations. See the following construction note.

The exact LCC construction is subtler than the pseudocode suggests: $f$ is a function of $K$ inputs jointly, and $u(\beta_j) = \mathbf{x}_j$ for each $j$ . The master interpolates the polynomial $g$ and then evaluates at a specific point that encodes the target combination. See Yu et al. 2019 §III for the full formulation.

Theorem: LCC Recovery Threshold

Let $f$ be a multivariate polynomial of $K$ vector-valued inputs with total degree $d_f$ . The Lagrange Coded Computing scheme with $N$ workers over $\mathbb{F}_q$ ( $q \geq N$ ) satisfies:

Correctness. Any $K_{\text{rec}} = d_f (K - 1) + 1$ responses suffice to recover $f(\mathbf{x}_1, \ldots, \mathbf{x}_K)$ .
Optimality. This matches the information-theoretic lower bound: no scheme can achieve smaller $K_{\text{rec}}$ at the same per-worker storage for polynomial functions of degree $d_f$ .
Per-worker storage. Each worker stores one "input-sized" evaluation ( $\mathbb{F}_q^d$ ) — the same as the standard polynomial code.

Specializing $f$ recovers earlier results:

Matrix multiplication: $d_f = 2$ (bilinear), $K_{\text{rec}} = 2(K - 1) + 1 = 2K - 1$ . For $(p, q)$ -partitioned matmul with $K = pq$ , $K_{\text{rec}} = pq$ — matching the standard polynomial code.
Convolution: $d_f = 2$ , same formula. For $(p, q)$ -partitioned convolution with $K = p + q - 1$ , $K_{\text{rec}} = p + q - 1$ — matching the entangled code.
Higher-degree polynomials: $d_f = 3, 4, \ldots$ require more responses, linearly in $d_f$ .

LCC reduces arbitrary polynomial computations to polynomial interpolation. The encoding lifts $K$ input vectors to a polynomial $u(z)$ whose evaluation at $\beta_j$ recovers input $\mathbf{x}_j$ . The function $f$ , being polynomial of degree $d_f$ in its inputs, becomes a polynomial of degree $d_f(K - 1)$ in $z$ when evaluated on $u(z)$ . This higher-degree polynomial is interpolated from $d_f(K - 1) + 1$ worker responses, and the target output is read off at a specific $\beta$ -value.

The framework's power is its generality: any polynomial function gets an optimal recovery threshold without specialized design.

Proof

Correctness

The polynomial $g(z) = f(u(z))$ has degree at most $d_f \cdot (K - 1)$ (since $u$ has degree $K - 1$ and $f$ has total degree $d_f$ ). Any $d_f(K - 1) + 1$ evaluations determine $g$ uniquely (Lagrange interpolation), and evaluating at the interpolation point appropriate to the target combination recovers $f(\mathbf{x}_1, \ldots, \mathbf{x}_K)$ .

Optimality

A counting argument: $f$ has at least $d_f(K - 1) + 1$ degrees of freedom as a polynomial on $u(z)$ , so the master needs at least that many independent observations. Matching achievability closes the rate region.

Specializations

Matmul: $d_f = 2$ , $K = pq$ , gives $K_{\text{rec}} = 2K - 1 = 2pq - 1$ . Wait — this is not the standard polynomial-code $K = pq$ exactly; LCC is tight up to constants. For convolution with $K = p + q - 1$ , $K_{\text{rec}} = 2K - 1 = 2(p + q - 1) - 1$ , larger than entangled's $K = p + q - 1$ .

The subtlety: for specific structured operations (matmul, convolution), specialized codes can beat LCC by exploiting the output structure beyond raw polynomial degree. LCC is "optimal for generic polynomials" but structured variants can do better. See Yu et al. 2019 Cor. 1. $\blacksquare$

Example: LCC for a Quadratic Function $f(\mathbf{x}) = \mathbf{x}^T \mathbf{A} \mathbf{x}$

Use LCC to distribute the computation of $f(\mathbf{x}) = \mathbf{x}^T \mathbf{A} \mathbf{x}$ (quadratic form) with data split into $K = 4$ partitions. Compute the recovery threshold.

Solution

Degree of $f$

$f$ is quadratic in $\mathbf{x}$ — total degree $d_f = 2$ .

LCC recovery threshold

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

Interpretation

With $N \geq 7$ workers, the master can recover $\mathbf{x}^T \mathbf{A} \mathbf{x}$ from any 7 responses. Straggler tolerance: $N - 7$ .

Comparison

A naive "compute each partition's quadratic independently" would require $K = 4$ responses but only handles diagonal contributions; the cross-partition terms $\mathbf{x}_i^T \mathbf{A}_{ij} \mathbf{x}_j$ require additional structure. LCC handles this transparently.

LCC Recovery Threshold vs. Function Degree

Plot the LCC recovery threshold $K_{\text{rec}} = d_f(K - 1) + 1$ as a function of the function degree $d_f$ for several input-count values $K$ . Higher-degree functions require more responses. This scaling reflects the fundamental cost of coded-computing generality: the more complex the target function, the more responses the master needs.

Parameters

K

— inputs8

Number of input partitions

d_f

max — function degree5

Lagrange Coded Computing: The Unified Framework

Animation of the LCC framework: inputs are lifted to a Lagrange polynomial, each worker computes

f

on its encoded input, master interpolates the degree-

d_f(K-1)

output polynomial from

K_{\text{rec}}

responses.

LCC vs. Specialized Coded-Computing Schemes

Target operation	Specialized scheme	$K_{\text{rec}}$	LCC	$K_{\text{rec}}^{\text{LCC}}$
Matrix mult $\mathbf{A}^T \mathbf{B}$	Polynomial code (Ch. 5)	$K = pq$	General	$K_{\text{rec}} = 2pq - 1$
Convolution $\mathbf{a} * \mathbf{b}$	Entangled polynomial (§8.2)	$K = p + q - 1$	General	$K_{\text{rec}} = 2(p+q-1) - 1$
Cubic / quartic polynomial	No specialized scheme	–	LCC	$K_{\text{rec}} = d_f(K-1) + 1$
Tensor contraction (order 3)	Entangled variant	$K = p + q + r - 2$	General	$K_{\text{rec}} = 3K - 2$
Arbitrary multivariate polynomial	No specialized scheme	–	LCC	$K_{\text{rec}} = d_f(K-1) + 1$

When to Use Which

The rule of thumb:

Specialized schemes (polynomial code, entangled polynomial, MatDot) are tighter for their target operations. Use them when the operation is well- specified and high straggler tolerance is critical.
LCC is more general but pays a constant-factor penalty in recovery threshold. Use it for arbitrary polynomial functions (especially higher-degree ones like polynomial activations in certain neural net designs) where no specialized code is available.
Hybrid: in production ML pipelines, use specialized schemes per-operation type (matmul, convolution) and LCC only for unusual operations that don't fit the standard patterns.

LCC's main value is generality: one algorithm for every polynomial computation. Its cost is that specialized knowledge (like convolution's reduced output structure) gets discarded.

Common Mistake: LCC Requires Polynomial Functions

Mistake:

Apply LCC to non-polynomial operations (ReLU, softmax, cross-entropy loss).

Correction:

LCC's correctness crucially depends on $f$ being a polynomial of bounded degree. For non-polynomial operations, LCC does not apply directly. Approaches:

Polynomial approximation. Approximate the non-polynomial $f$ by a low-degree polynomial $\hat f$ , apply LCC to $\hat f$ , tolerate the approximation error.
Hybrid coding. Apply LCC to the polynomial layers of a network (convolutions, matmuls) and compute the non-polynomial layers redundantly / with replication.
Secure MPC. For operations like ReLU, use cryptographic MPC protocols instead of coded computing.

None of these is as clean as the polynomial LCC framework; non-polynomial coded computing remains an open research direction.

🔧Engineering Note

LCC in Production: A Niche Tool

LCC has seen limited production adoption, primarily because:

Overhead. The $d_f(K - 1) + 1$ recovery threshold is constant-factor worse than specialized schemes for common operations.
Typical ML doesn't need arbitrary polynomial computations. Most modern ML layers are either bilinear (matmul, convolution — handled by specialized codes) or non-polynomial (ReLU, softmax — not handled by LCC).
Niche use. Quartic polynomial activations, some privacy-preserving deep-net architectures (where multiplications are squared for exact MPC compatibility), and certain cryptographic ML pipelines.

In research-level deployments, LCC has been used for privacy-preserving logistic regression (quadratic sigmoid approximation) and for federated computation of higher-order statistics (e.g., skewness, kurtosis in federated analytics).

Practical Constraints

•
LCC overhead: constant-factor worse than specialized schemes
•
Most modern ML operations not served by LCC directly
•
Niche applications: privacy-preserving quadratic-activation models, federated analytics

📋 Ref: Yu et al. 2019 §VI; TF-Encrypted research toolkit

Key Takeaway

Lagrange Coded Computing unifies the coded-computing framework for arbitrary multivariate-polynomial functions. Recovery threshold is $K_{\text{rec}} = d_f(K - 1) + 1$ . Specialized schemes (polynomial codes, entangled codes) are tighter for specific bilinear operations; LCC is the general fallback for arbitrary polynomial computations.

Historical Note: The LCC Paper

2019–present

Qian Yu, Netanel Raviv, Mahtab Soleymani, and A. Salman Avestimehr's 2019 paper "Lagrange Coded Computing: Optimal Design for Resiliency, Security, and Privacy" was a capstone on the polynomial-code research programme: it unified the various specialized schemes into a single framework and showed that Lagrange interpolation on polynomial-coded inputs is optimal for arbitrary polynomial functions. The paper won the IEEE IT Society's James L. Massey Research and Teaching Award and is considered a landmark in the coded-computing literature. Subsequent work has extended LCC to privacy ( $T$ -private LCC, Soleymani et al. 2021) and to Byzantine robustness (Solanki et al. 2020), setting the stage for Part III's secure-computation chapters.

Quick Check

For a bilinear function ( $d_f = 2$ ) with $K = 10$ inputs, what is the LCC recovery threshold?

$K_{\text{rec}} = 19$

$K_{\text{rec}} = 10$

$K_{\text{rec}} = 100$

$K_{\text{rec}} = 2$