Prerequisites & Notation

Before You Begin

Chapter 5 is the headline chapter of Part II. It develops the polynomial-code construction for coded distributed matrix multiplication — arguably the most influential coded-computing result of the last decade. The prerequisites are the finite-field algebra of Chapter 3, the IA framework of Chapter 4, and standard block-matrix arithmetic. Readers who have internalized the "polynomial evaluation + Lagrange interpolation" pattern from Chapter 3 will find the main construction almost immediate.

Finite fields and polynomial arithmetic (Chapter 3)(Review ch03)
Self-check: Can you reconstruct a degree- $d$ polynomial from $d + 1$ distinct evaluations over $\mathbb{F}_q$ (with $q > d$ )?
IA framework for coded matrix multiplication (Chapter 4 §4.2)(Review ch04)
Self-check: Why is the recovery threshold $K \geq pq$ ?
Block-matrix multiplication and transposes
Self-check: If $\mathbf{A} = [\mathbf{A}_1, \mathbf{A}_2]$ and $\mathbf{B} = [\mathbf{B}_1, \mathbf{B}_2]$ , what is $\mathbf{A}^T \mathbf{B}$ in block form?
MDS codes (Reed-Solomon)(Review ch09)
Self-check: What is the minimum distance of an $(n, k)$ MDS code, and what does the Singleton bound say?
Straggler-tolerance recovery threshold (Chapter 1)(Review ch01)
Self-check: For i.i.d. exponential completion times, how does $\mathbb{E}[T_{(K)}]$ vary with $K \leq N$ ?

Notation for This Chapter

The central object is the polynomial $p(x)$ whose evaluations at distinct points form the workers' encoded matrices. $K$ is the recovery threshold; $(p, q)$ are the column partitions of $\mathbf{A}, \mathbf{B}$ . We use boldface for matrices and distinguish the privacy threshold $T$ (Section 5.4) from the straggler-tolerance parameter $N - K$ .

Symbol	Meaning	Introduced
$\mathbf{A}, \mathbf{B}$	Input matrices of sizes $m \times d$ and $m \times d'$ resp.	s01
$\mathbf{A}^T \mathbf{B}$	Desired output, size $d \times d'$	s01
$p, q$	Column partitions of $\mathbf{A}$ and $\mathbf{B}$ respectively	s01
$\mathbf{A}_i, \mathbf{B}_j$	$i$ -th and $j$ -th column blocks	s01
$\mathbf{C}_{ij} = \mathbf{A}_i^T \mathbf{B}_j$	Block $(i, j)$ of the output (to be reconstructed)	s01
$N$	Number of workers	s01
$K$	Recovery threshold (min. responses to reconstruct)	s02
$p(x)$	Encoding polynomial, degree $pq - 1$	s02
$\alpha_k$	Evaluation point for worker $k$	s02
$\mu$	Per-worker storage fraction = $1/p + 1/q$ in basic scheme	s02
$T$	Privacy threshold (number of colluding workers) — Section 5.4	s04
$\mathbb{F}_q$	Finite field; $q \geq N$ for distinct evaluation points	s02

← Ch 4 The Distributed Matrix-Multiplication Problem