# Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Aug 2017.

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

- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [A Tighter Complexity Analysis of SparseGPT](https://mlsanity.com/paper/2408.12151/) (2024)
- [Better Neural Network Expressivity: Subdividing the Simplex](https://mlsanity.com/paper/2505.14338/) (2025)
- [DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2107.02736/) (2021)
- [Fast John Ellipsoid Computation with Differential Privacy Optimization](https://mlsanity.com/paper/2408.06395/) (2024)
- [Subquadratic Kronecker Regression with Applications to Tensor Decomposition](https://mlsanity.com/paper/2209.04876/) (2022)
- [The I/O Complexity of Attention, or How Optimal is Flash Attention?](https://mlsanity.com/paper/2402.07443/) (2024)
- [Fast algorithm for overcomplete order-3 tensor decomposition](https://mlsanity.com/paper/2202.06442/) (2022)
- [Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities](https://mlsanity.com/paper/2507.04438/) (2025)
- [Fine-Grained Complexity and Algorithms for the Schulze Voting Method](https://mlsanity.com/paper/2103.03959/) (2021)
- [Agnostic PAC Learning of k-juntas Using L2-Polynomial Regression](https://mlsanity.com/paper/2303.04859/) (2023)
- [Fast Riemannian-manifold Hamiltonian Monte Carlo for hierarchical Gaussian-process models](https://mlsanity.com/paper/2511.06407/) (2025)

## Abstract (arXiv)

In the past few years, successive improvements of the asymptotic complexity of square matrix multiplication have been obtained by developing novel methods to analyze the powers of the Coppersmith-Winograd tensor, a basic construction introduced thirty years ago. In this paper we show how to generalize this approach to make progress on the complexity of rectangular matrix multiplication as well, by developing a framework to analyze powers of tensors in an asymmetric way. By applying this methodology to the fourth power of the Coppersmith-Winograd tensor, we succeed in improving the complexity of rectangular matrix multiplication. Let α denote the maximum value such that the product of an n× nα matrix by an nα× n matrix can be computed with O(n2+ε) arithmetic operations for any ε>0. By analyzing the fourth power of the Coppersmith-Winograd tensor using our methods, we obtain the new lower bound α>0.31389, which improves the previous lower bound α>0.30298 obtained five years ago by Le Gall (FOCS'12) from the analysis of the second power of the Coppersmith-Winograd tensor. More generally, we give faster algorithms computing the product of an n× nk matrix by an nk× n matrix for any value kneq 1. (In the case k=1, we recover the bounds recently obtained for square matrix multiplication). These improvements immediately lead to improvements in the complexity of a multitude of fundamental problems for which the bottleneck is rectangular matrix multiplication, such as computing the all-pair shortest paths in directed graphs with bounded weights.