# Faster Matrix Multiplication via Asymmetric Hashing

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

## Key facts

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

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

- [Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time](https://mlsanity.com/paper/2302.11068/) (2023)
- [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)
- [Optimal Quantization for Matrix Multiplication](https://mlsanity.com/paper/2410.13780/) (2024)
- [Strassen Attention, Split VC Dimension and Compositionality in Transformers](https://mlsanity.com/paper/2501.19215/) (2025)
- [Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters](https://mlsanity.com/paper/2311.14823/) (2023)
- [Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games](https://mlsanity.com/paper/2304.14197/) (2023)
- [Convergence of Two-Layer Regression with Nonlinear Units](https://mlsanity.com/paper/2308.08358/) (2023)
- [Arbitrary Polynomial Separations in Trainable Quantum Machine Learning](https://mlsanity.com/paper/2402.08606/) (2024)
- [Multiparticle Kalman filter for object localization in symmetric environments](https://mlsanity.com/paper/2303.07897/) (2023)
- [Approximation and bounding techniques for the Fisher-Rao distances between parametric statistical models](https://mlsanity.com/paper/2403.10089/) (2024)
- [Similarity and Dissimilarity Guided Co-association Matrix Construction for Ensemble Clustering](https://mlsanity.com/paper/2411.00904/) (2024)
- [Improving the matrix multiplication exponent with modern optimization and AlphaEvolve](https://mlsanity.com/paper/2608.16884/) (2026)
- [Inference for Probabilistic Dependency Graphs](https://mlsanity.com/paper/2311.05580/) (2023)
- [Sublinear Time Quantum Algorithm for Attention Approximation](https://mlsanity.com/paper/2602.00874/) (2026)
- [Halpern Iteration Achieves tildeO(ε-1/p) pth-Order Oracle Complexity for Monotone Variational Inequalities](https://mlsanity.com/paper/2608.08463/) (2026)
- [Efficiently-Verifiable Strong Uniquely Solvable Puzzles and Matrix Multiplication](https://mlsanity.com/paper/2307.06463/) (2023)
- [Universal Matrix Multiplication on Quantum Computer](https://mlsanity.com/paper/2408.03085/) (2024)
- [Reducing the Complexity of Matrix Multiplication by Quantum Computing](https://mlsanity.com/paper/2602.05541/) (2026)
- [Optimal High-Order Methods for Solving Monotone Variational Inequalities](https://mlsanity.com/paper/2609.23557/) (2026)

## Abstract (arXiv)

Fast matrix multiplication is one of the most fundamental problems in algorithm research. The exponent of the optimal time complexity of matrix multiplication is usually denoted by ω. This paper discusses new ideas for improving the laser method for fast matrix multiplication. We observe that the analysis of higher powers of the Coppersmith-Winograd tensor [Coppersmith & Winograd 1990] incurs a "combination loss", and we partially compensate for it using an asymmetric version of CW's hashing method. By analyzing the eighth power of the CW tensor, we give a new bound of ω<2.371866, which improves the previous best bound of ω<2.372860 [Alman & Vassilevska Williams 2020]. Our result breaks the lower bound of 2.3725 in [Ambainis, Filmus & Le Gall 2015] because of the new method for analyzing component (constituent) tensors.