# CodedSketch: A Coding Scheme for Distributed Computation of Approximated Matrix Multiplication

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Dec 2018.

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

- [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)
- [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)
- [Game of Coding With an Unknown Adversary](https://mlsanity.com/paper/2502.07109/) (2025)
- [Optimal Communication-Computation Trade-Off in Heterogeneous Gradient Coding](https://mlsanity.com/paper/2103.01589/) (2021)
- [Gradient Coding with Iterative Block Leverage Score Sampling](https://mlsanity.com/paper/2308.03096/) (2023)
- [Game of Coding: Coding Theory in the Presence of Rational Adversaries, Motivated by Decentralized Machine Learning](https://mlsanity.com/paper/2601.02313/) (2026)
- [Privacy-aware Berrut Approximated Coded Computing for Federated Learning](https://mlsanity.com/paper/2405.01704/) (2024)
- [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)
- [A Learning-Based Approach to Approximate Coded Computation](https://mlsanity.com/paper/2205.09818/) (2022)
- [Successive Refinement in Large-Scale Computation: Advancing Model Inference Applications](https://mlsanity.com/paper/2402.07229/) (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)
- [Learning-Theoretic Foundation for General Coded Computing: The Straggler Setting](https://mlsanity.com/paper/2608.28910/) (2026)

## Abstract (arXiv)

In this paper, we propose CodedSketch, as a distributed straggler-resistant scheme to compute an approximation of the multiplication of two massive matrices. The objective is to reduce the recovery threshold, defined as the total number of worker nodes that we need to wait for to be able to recover the final result. To exploit the fact that only an approximated result is required, in reducing the recovery threshold, some sorts of pre-compression are required. However, compression inherently involves some randomness that would lose the structure of the matrices. On the other hand, considering the structure of the matrices is crucial to reduce the recovery threshold. In CodedSketch, we use count--sketch, as a hash-based compression scheme, on the rows of the first and columns of the second matrix, and a structured polynomial code on the columns of the first and rows of the second matrix. This arrangement allows us to exploit the gain of both in reducing the recovery threshold. To increase the accuracy of computation, multiple independent count--sketches are needed. This independency allows us to theoretically characterize the accuracy of the result and establish the recovery threshold achieved by the proposed scheme. To guarantee the independency of resulting count--sketches in the output, while keeping its cost on the recovery threshold minimum, we use another layer of structured codes.