Chapter 5: Coded Matrix Multiplication

Learning Objectives

• Formulate distributed matrix multiplication $\mathbf{A}^T\mathbf{B}$ as a coded-computing problem with storage/recovery trade-offs
• Construct the polynomial code (Yu–Maddah-Ali–Avestimehr) for arbitrary partition counts $(p, q)$
• Prove that the polynomial code's recovery threshold $K = pq$ matches the information-theoretic lower bound
• Compare polynomial codes with MDS-coded replication, plain replication, and entangled polynomial codes in terms of $(K, \mu, q)$
• Add privacy: extend polynomial codes to $T$-private matrix multiplication by padding with $T$ random blocks
• Characterize numerical precision, field size, and decoding complexity in practical deployments