More Asymmetry Yields Faster Matrix Multiplication
Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei Zhou
Abstract
We present a new improvement on the laser method for designing fast matrix multiplication algorithms. The new method further develops the recent advances by [Duan, Wu, Zhou FOCS 2023] and [Vassilevska Williams, Xu, Xu, Zhou SODA 2024]. Surprisingly the new improvement is achieved by incorporating more asymmetry in the analysis, circumventing a fundamental tool of prior work that requires two of the three dimensions to be treated identically. Together with recent advances in numerical optimization [Dupont et al. arXiv:2608.16884], the method yields a new bound on the square matrix multiplication exponent ω < 2.371177, improved from the previous bound of ω < 2.371552. We also improve the bounds of the exponents for multiplying rectangular matrices of various shapes.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Your agent calls
Luneget_paper_fulltext
Free to start. No credit card required.
Terminal
Install the CLIlune papers fulltext 68b81320-e0e7-40d3-a74b-949ca3720011Cited by top-tier papers29
- Consistent Low-Rank ApproximationDavid Woodruff, Samson ZhouICLR 2026 · 62 citations
- No Exponential Quantum Speedup for SIS∞ AnymoreRobin Kothari, Ryan O'Donnell, Kewen WuSTOC 2026 · 12 citations
- Error-Correction of Matrix Multiplication AlgorithmsShuichi Hirahara, Nobutaka ShimizuSTOC 2025 · 5 citations
- Subquadratic Algorithms and Hardness for Attention with Any TemperatureShreya Gupta, Boyang Huang, Barna Saha, Yinzhan Xu et al.ICLR 2026 · 5 citations
- Invariant subspaces and PCA in nearly matrix multiplication timeAleksandros Sobczyk, Marko Mladenovic, Mathieu LuisierNeurIPS 2024 · 4 citations
Builds on4
- A Refined Laser Method and Faster Matrix MultiplicationJosh Alman, Virginia Vassilevska WilliamsSODA 2021 · 275 citations
- New Bounds for Matrix Multiplication: from Alpha to OmegaVirginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei ZhouSODA 2024 · 90 citations
- Faster Matrix Multiplication via Asymmetric HashingRan Duan, Hongxun Wu, Renfei ZhouFOCS 2023 · 54 citations
- Faster Rectangular Matrix Multiplication by Combination Loss AnalysisFrançois Le GallSODA 2024 · 8 citations
Related papers
- Improving the Leading Constant of Matrix MultiplicationJosh Alman, Hantao YuSODA 2025 · 2 citations
- The Time Complexity of Fully Sparse Matrix MultiplicationAmir Abboud, Karl Bringmann, Nick Fischer, Marvin KünnemannSODA 2024 · 6 citations
- Faster Algorithms for Bounded-Difference Min-Plus ProductShucheng Chi, Ran Duan, Tianle XieSODA 2022 · 5 citations
- Faster min-plus product for monotone instancesShucheng Chi, Ran Duan, Tianle Xie, Tianyi ZhangSTOC 2022 · 12 citations
- An improved cutting plane method for convex optimization, convex-concave games, and its applicationsHaotian Jiang, Yin Tat Lee, Zhao Song, Sam Chiu-wai WongSTOC 2020 · 54 citations
