mlsanityData to 14 Oct 2026

On the Optimal Recovery Threshold of Coded Matrix Multiplication

arXiv 1801.10292 ↗First posted 31 Jan 2018cs.IT cs.DC math.ITcited by 27

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 5; 2022: 8; 2023: 5; 2024: 2; 2025: 3; 2026: 4.

27 papers.

Sort:

  1. 2021CodedPaddedFL and CodedSecAgg: Straggler Mitigation and Secure Aggregation in Federated Learningcited by 20
  2. 2021Gradient Coding with Dynamic Clustering for Straggler-Tolerant Distributed Learningcited by 8
  3. 2021List-Decodable Coded Computing: Breaking the Adversarial Toleration Barriercited by 4
  4. 2021Coding for Straggler Mitigation in Federated Learningcited by 4
  5. 2023ByzSecAgg: A Byzantine-Resistant Secure Aggregation Scheme for Federated Learning Based on Coded Computing and Vector Commitmentcited by 4
  6. 2025General Coded Computing: Adversarial Settingscited by 4
  7. 2022Straggler-Resilient Differentially-Private Decentralized Learningcited by 3
  8. 2021Optimal Communication-Computation Trade-Off in Heterogeneous Gradient Codingcited by 2
  9. 2022Adaptive Stochastic Gradient Descent for Fast and Communication-Efficient Distributed Learningcited by 2
  10. 2023Gradient Coding with Iterative Block Leverage Score Samplingcited by 2
  11. 2025General Coded Computing in a Probabilistic Straggler Regimecited by 2
  12. 2026Game of Coding: Coding Theory in the Presence of Rational Adversaries, Motivated by Decentralized Machine Learningcited by 2
15 more
  1. 2022Lightweight Projective Derivative Codes for Compressed Asynchronous Gradient Descentcited by 1
  2. 2022Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learningcited by 1
  3. 2022Sequential Gradient Coding For Straggler Mitigationcited by 1
  4. 2023Randomized Polar Codes for Anytime Distributed Machine Learningcited by 1
  5. 2025Privacy-aware Berrut Approximated Coded Computing applied to general distributed learningcited by 1
  6. 2022Random Alloy Codes and the Fundamental Limits of Coded Distributed Tensorscited by 0
  7. 2022Generalized Lagrange Coded Computing: A Flexible Computation-Communication Tradeoff for Resilient, Secure, and Private Computationcited by 0
  8. 2022A Learning-Based Approach to Approximate Coded Computationcited by 0
  9. 2023Coded Matrix Computations for D2D-enabled Linearized Federated Learningcited by 0
  10. 2023Fast and Straggler-Tolerant Distributed SGD with Reduced Computation Loadcited by 0
  11. 2024Successive Refinement in Large-Scale Computation: Advancing Model Inference Applicationscited by 0
  12. 2024Flexible Coded Distributed Convolution Computing for Enhanced Straggler Resilience and Numerical Stability in Distributed CNNscited by 0
  13. 2026Learning from Acceptance: Cumulative Regret in the Game of Codingcited by 0
  14. 2026Learning-Theoretic Foundation for General Coded Computing: The Straggler Settingcited by 0
  15. 2026Manifold-Aware General Coded Computing for Straggler-Resilient Distributed Computingcited by 0