Research map / Learning theory and algorithms / Matrix and tensor methods
Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Design worker computations so their products are evaluations of a degree-(mn-1) polynomial | Distributed matrix multiplication · Distributed matrix multiplication | recovery threshold: mn | Helped |
| Replace 1D MDS coding with polynomial coding | Distributed matrix multiplication · Distributed matrix multiplication | recovery threshold: N-\frac{N}{n}+m -> mn | Helped |
| Replace product coding with polynomial coding | Distributed matrix multiplication (m=n) · Distributed matrix multiplication | recovery threshold: 2(m-1)\sqrt{N}-(m-1)^2+1 -> mn | Helped |
| Use polynomial coding so any mn worker results suffice | Distributed matrix multiplication · Distributed matrix multiplication | computation latency: T\geq T_{\textup{poly}} | Helped |
| Use polynomial coding | Distributed matrix multiplication · Distributed matrix multiplication | communication load: rt \log_2 q | Helped |
| Use polynomial coding instead of uncoded computation | Distributed matrix multiplication on AWS EC2 · AWS EC2 matrix multiplication with a straggler | tail latency: 37% | Helped |
| Set polynomial-code parameters α=β=1, allowing terms for the same output coefficient to combine (ablation) | Distributed convolution · Distributed convolution | recovery threshold: mn -> m+n-1 | Helped |
| Use the naive polynomial code that recovers all individual convolution components instead of the α=β=1 variation (ablation) | Distributed convolution · Distributed convolution | recovery threshold: m+n-1 -> mn | Hurt |
| Use deterministic polynomial coding instead of random linear combinations | Distributed matrix multiplication · Distributed matrix multiplication | decoding complexity: O(m^3n^3+mnrt) | Helped |
Closest papers by meaning
- The Structural Complexity of Matrix-Vector Multiplication (NeurIPS 2025 · similarity 0.83)
- QiMeng-GEMM: Automatically Generating High-Performance Matrix Multiplication Code by Exploiting Large Language Models (AAAI 2025 · similarity 0.82)
- LibAMM: Empirical Insights into Approximate Computing for Accelerating Matrix Multiplication (NeurIPS 2024 · similarity 0.81)
- Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions (ICLR 2025 · similarity 0.81)
- Coded Computing for Resilient Distributed Computing: A Learning-Theoretic Framework (NeurIPS 2024 · similarity 0.80)
- Improving the Worst-Case Bidirectional Communication Complexity for Nonconvex Distributed Optimization under Function Similarity (NeurIPS 2024 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.