Prerequisites & Notation

Before You Begin

Chapter 8 closes Part II by generalizing the polynomial-code framework of Chapter 5 to richer computational primitives: convolutions, matrix-vector products at scale, and general multivariate-polynomial tensor operations. The prerequisites are the polynomial-code background of Chapter 5 and comfort with tensor notation from basic linear algebra.

Polynomial codes (Chapter 5)(Review ch05)
Self-check: Write the encoding polynomials $p_A, p_B$ and state the recovery threshold $K = pq$ .
Gradient coding (Chapter 6)(Review ch06)
Self-check: Why is gradient coding a specialization of polynomial codes to $q = 1$ ?
Tensor notation and the Kronecker product(Review ch01)
Self-check: What is the relationship between $(\mathbf{A} \otimes \mathbf{B})\text{vec}(\mathbf{X})$ and $\text{vec}(\mathbf{A}\mathbf{X}\mathbf{B}^T)$ ?
Convolution: 1D, 2D, and their polynomial representations
Self-check: If $c = a * b$ (linear convolution), what is the relationship between the generating polynomials $p_a(x) p_b(x) = p_c(x)$ ?
Multivariate polynomials and Lagrange interpolation(Review ch03)
Self-check: For $f(x) = \sum_i c_i L_i(x)$ (Lagrange form), what does the collection $\{f(\alpha_k)\}$ tell you about the coefficients $c_i$ ?

Notation for This Chapter

Tensor operations introduce new notation. We write tensors in bold upper-case ( $\mathbf{A}, \mathbf{B}, \mathbf{T}$ ) and convolution as $*$ . The generating polynomial of a tensor along one axis is denoted $p_{\mathbf{A}}(x)$ . The Lagrange Coded Computing framework uses interpolation points $\beta_1, \ldots, \beta_K$ and evaluation points $\alpha_1, \ldots, \alpha_N$ .

Symbol	Meaning	Introduced
$\mathbf{A} \in \mathbb{F}_q^{m \times d}$	Input matrix (same as Chapter 5)	s01
$\mathbf{T} \in \mathbb{F}_q^{d_1 \times \cdots \times d_r}$	Tensor of order $r$ (generalizes matrices)	s01
$*$	Linear convolution (1D or 2D)	s01
$p, q$	Partition counts (same role as Chapter 5)	s02
$K$	Recovery threshold (minimum responses)	s02
$\beta_1, \ldots, \beta_K$	Lagrange interpolation points at which master evaluates the target function	s03
$\alpha_1, \ldots, \alpha_N$	Evaluation points assigned to workers	s03
$f: (\mathbb{F}_q^d)^K \to \mathbb{F}_q^{d'}$	Target function: a $K$ -variate polynomial over vectors	s03
$d_f$	Degree of the target function $f$	s03

← Ch 7 Beyond Matrix Multiplication