# On the Optimal Recovery Threshold of Coded Matrix Multiplication

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jan 2018.

## Built on by (most cited first, 27 of 27)

- [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)
- [List-Decodable Coded Computing: Breaking the Adversarial Toleration Barrier](https://mlsanity.com/paper/2101.11653/) (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)
- [Straggler-Resilient Differentially-Private Decentralized Learning](https://mlsanity.com/paper/2212.03080/) (2022)
- [Optimal Communication-Computation Trade-Off in Heterogeneous Gradient Coding](https://mlsanity.com/paper/2103.01589/) (2021)
- [Adaptive Stochastic Gradient Descent for Fast and Communication-Efficient Distributed Learning](https://mlsanity.com/paper/2208.03134/) (2022)
- [Gradient Coding with Iterative Block Leverage Score Sampling](https://mlsanity.com/paper/2308.03096/) (2023)
- [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)
- [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)
- [Coded Matrix Computations for D2D-enabled Linearized Federated Learning](https://mlsanity.com/paper/2302.12305/) (2023)
- [Fast and Straggler-Tolerant Distributed SGD with Reduced Computation Load](https://mlsanity.com/paper/2304.08589/) (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)
- [Learning from Acceptance: Cumulative Regret in the Game of Coding](https://mlsanity.com/paper/2605.09754/) (2026)
- [Learning-Theoretic Foundation for General Coded Computing: The Straggler Setting](https://mlsanity.com/paper/2608.28910/) (2026)
- [Manifold-Aware General Coded Computing for Straggler-Resilient Distributed Computing](https://mlsanity.com/paper/2609.00552/) (2026)

## Abstract (arXiv)

We provide novel coded computation strategies for distributed matrix-matrix products that outperform the recent "Polynomial code" constructions in recovery threshold, i.e., the required number of successful workers. When m-th fraction of each matrix can be stored in each worker node, Polynomial codes require m2 successful workers, while our MatDot codes only require 2m-1 successful workers, albeit at a higher communication cost from each worker to the fusion node. We also provide a systematic construction of MatDot codes. Further, we propose "PolyDot" coding that interpolates between Polynomial codes and MatDot codes to trade off communication cost and recovery threshold. Finally, we demonstrate a coding technique for multiplying n matrices (n ≥ 3) by applying MatDot and PolyDot coding ideas.