Approximate Distributed Coded Computing: Polynomial Codes and Randomized Sketching
- 18 May 2026
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE BITS the Information Theory Magazine
- Vol. PP (26924080) , 1-15
Abstract
Coded computing is a distributed paradigm that uses coding theory to introduce redundancy and overcome bottlenecks in large-scale systems. In the same vein, randomized numerical linear algebra employs probabilistic methods to compress and accelerate linear algebraic operations, addressing challenges in high-dimensional data analysis. This article reviews the foundations of both fields and presents distributed schemes that combine techniques from both to speed up optimization and machine learning algorithms, in the presence of slow or non-responsive servers. Along the way, we touch on various related topics and mathematical concepts.Keywords
All Related Versions
Funding Information
- NSF TRIPODS Phase II (2217058)
This publication has 22 references indexed in Scilit:
- Compression-Informed Coded Computing2023
- Numerically stable coded matrix computations via circulant and rotation matrix embeddings2021
- Approximate Weighted C R Coded Matrix Multiplication2021
- Weighted Gradient Coding with Leverage Score Sampling2020
- Gradient Coding Based on Block Designs for Mitigating Adversarial Stragglers2019
- Random Sampling for Distributed Coded Matrix Multiplication2019
- OverSketch: Approximate Matrix Multiplication for the Cloud2018
- Improving Distributed Gradient Descent Using Reed-Solomon Codes2018
- Encoded distributed optimization2017
- High-dimensional coded matrix multiplication2017