# Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication

arXiv: https://arxiv.org/abs/1705.10464 · HTML: https://mlsanity.com/paper/1705.10464/

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 May 2017.

## Built on by (most cited first, 30 of 32)

- [Multiplying Matrices Without Multiplying](https://mlsanity.com/paper/2106.10860/) (2021)
- [CodedPaddedFL and CodedSecAgg: Straggler Mitigation and Secure Aggregation in Federated Learning](https://mlsanity.com/paper/2112.08909/) (2021)
- [Gradient Coding with Dynamic Clustering for Straggler-Tolerant Distributed Learning](https://mlsanity.com/paper/2103.01206/) (2021)
- [ApproxIFER: A Model-Agnostic Approach to Resilient and Robust Prediction Serving Systems](https://mlsanity.com/paper/2109.09868/) (2021)
- [Coded Computing for Resilient Distributed Computing: A Learning-Theoretic Framework](https://mlsanity.com/paper/2406.00300/) (2024)
- [List-Decodable Coded Computing: Breaking the Adversarial Toleration Barrier](https://mlsanity.com/paper/2101.11653/) (2021)
- [Adaptive Verifiable Coded Computing: Towards Fast, Secure and Private Distributed Machine Learning](https://mlsanity.com/paper/2107.12958/) (2021)
- [Coding for Straggler Mitigation in Federated Learning](https://mlsanity.com/paper/2109.15226/) (2021)
- [ByzSecAgg: A Byzantine-Resistant Secure Aggregation Scheme for Federated Learning Based on Coded Computing and Vector Commitment](https://mlsanity.com/paper/2302.09913/) (2023)
- [General Coded Computing: Adversarial Settings](https://mlsanity.com/paper/2502.08058/) (2025)
- [Optimal Communication-Computation Trade-Off in Heterogeneous Gradient Coding](https://mlsanity.com/paper/2103.01589/) (2021)
- [General Coded Computing in a Probabilistic Straggler Regime](https://mlsanity.com/paper/2502.00645/) (2025)
- [Game of Coding: Coding Theory in the Presence of Rational Adversaries, Motivated by Decentralized Machine Learning](https://mlsanity.com/paper/2601.02313/) (2026)
- [Lightweight Projective Derivative Codes for Compressed Asynchronous Gradient Descent](https://mlsanity.com/paper/2201.12990/) (2022)
- [Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning](https://mlsanity.com/paper/2206.02450/) (2022)
- [Sequential Gradient Coding For Straggler Mitigation](https://mlsanity.com/paper/2211.13802/) (2022)
- [Randomized Polar Codes for Anytime Distributed Machine Learning](https://mlsanity.com/paper/2309.00682/) (2023)
- [Privacy-aware Berrut Approximated Coded Computing applied to general distributed learning](https://mlsanity.com/paper/2505.06759/) (2025)
- [mathsfVISTA: Decentralized Machine Learning in Adversary Dominated Environments](https://mlsanity.com/paper/2605.07841/) (2026)
- [Random Alloy Codes and the Fundamental Limits of Coded Distributed Tensors](https://mlsanity.com/paper/2202.03469/) (2022)
- [Generalized Lagrange Coded Computing: A Flexible Computation-Communication Tradeoff for Resilient, Secure, and Private Computation](https://mlsanity.com/paper/2204.11168/) (2022)
- [A Learning-Based Approach to Approximate Coded Computation](https://mlsanity.com/paper/2205.09818/) (2022)
- [Nested Gradient Codes for Straggler Mitigation in Distributed Machine Learning](https://mlsanity.com/paper/2212.08580/) (2022)
- [Coded Matrix Computations for D2D-enabled Linearized Federated Learning](https://mlsanity.com/paper/2302.12305/) (2023)
- [Successive Refinement in Large-Scale Computation: Advancing Model Inference Applications](https://mlsanity.com/paper/2402.07229/) (2024)
- [Flexible Coded Distributed Convolution Computing for Enhanced Straggler Resilience and Numerical Stability in Distributed CNNs](https://mlsanity.com/paper/2411.01579/) (2024)
- [DReS: Dual Reconstruction Smoothing for Functional Regularization](https://mlsanity.com/paper/2510.00253/) (2025)
- [Learning from Acceptance: Cumulative Regret in the Game of Coding](https://mlsanity.com/paper/2605.09754/) (2026)
- [Pipelined Gradient Coding](https://mlsanity.com/paper/2607.20739/) (2026)
- [Learning-Theoretic Foundation for General Coded Computing: The Straggler Setting](https://mlsanity.com/paper/2608.28910/) (2026)

## Abstract (arXiv)

We consider a large-scale matrix multiplication problem where the computation is carried out using a distributed system with a master node and multiple worker nodes, where each worker can store parts of the input matrices. We propose a computation strategy that leverages ideas from coding theory to design intermediate computations at the worker nodes, in order to efficiently deal with straggling workers. The proposed strategy, named as polynomial codes, achieves the optimum recovery threshold, defined as the minimum number of workers that the master needs to wait for in order to compute the output. Furthermore, by leveraging the algebraic structure of polynomial codes, we can map the reconstruction problem of the final output to a polynomial interpolation problem, which can be solved efficiently. Polynomial codes provide order-wise improvement over the state of the art in terms of recovery threshold, and are also optimal in terms of several other metrics. Furthermore, we extend this code to distributed convolution and show its order-wise optimality.