# A Refined Laser Method and Faster Matrix Multiplication

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

## Key facts

- Cited by 56 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Oct 2020.

## Built on by (most cited first, 30 of 56)

- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [SWARM Parallelism: Training Large Models Can Be Surprisingly Communication-Efficient](https://mlsanity.com/paper/2301.11913/) (2023)
- [Attention Scheme Inspired Softmax Regression](https://mlsanity.com/paper/2304.10411/) (2023)
- [Link Prediction with Persistent Homology: An Interactive View](https://mlsanity.com/paper/2102.10255/) (2021)
- [Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension](https://mlsanity.com/paper/2304.04397/) (2023)
- [An Iterative Algorithm for Rescaled Hyperbolic Functions Regression](https://mlsanity.com/paper/2305.00660/) (2023)
- [InfoPrompt: Information-Theoretic Soft Prompt Tuning for Natural Language Understanding](https://mlsanity.com/paper/2306.04933/) (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)
- [A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Models](https://mlsanity.com/paper/2306.02295/) (2023)
- [CASSPR: Cross Attention Single Scan Place Recognition](https://mlsanity.com/paper/2211.12542/) (2022)
- [Dynamic Tensor Product Regression](https://mlsanity.com/paper/2210.03961/) (2022)
- [Adjustment Identification Distance: A gadjid for Causal Structure Learning](https://mlsanity.com/paper/2402.08616/) (2024)
- [GRIL: A 2-parameter Persistence Based Vectorization for Machine Learning](https://mlsanity.com/paper/2304.04970/) (2023)
- [Scalable Decision-Focused Learning in Restless Multi-Armed Bandits with Application to Maternal and Child Health](https://mlsanity.com/paper/2202.00916/) (2022)
- [Solving Dense Linear Systems Faster Than via Preconditioning](https://mlsanity.com/paper/2312.08893/) (2023)
- [Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Acceleration](https://mlsanity.com/paper/2305.08367/) (2023)
- [BR-NS: an Archive-less Approach to Novelty Search](https://mlsanity.com/paper/2104.03936/) (2021)
- [Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters](https://mlsanity.com/paper/2311.14823/) (2023)
- [Fast John Ellipsoid Computation with Differential Privacy Optimization](https://mlsanity.com/paper/2408.06395/) (2024)
- [Ensemble Clustering via Co-association Matrix Self-enhancement](https://mlsanity.com/paper/2205.05937/) (2022)
- [Subquadratic Kronecker Regression with Applications to Tensor Decomposition](https://mlsanity.com/paper/2209.04876/) (2022)
- [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)
- [Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Sampling](https://mlsanity.com/paper/2107.10654/) (2021)
- [Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time](https://mlsanity.com/paper/2107.08090/) (2021)
- [The magnitude vector of images](https://mlsanity.com/paper/2110.15188/) (2021)
- [On the complexity of nonsmooth automatic differentiation](https://mlsanity.com/paper/2206.01730/) (2022)
- [Kernel Relative-prototype Spectral Filtering for Few-shot Learning](https://mlsanity.com/paper/2207.11685/) (2022)
- [Structural Node Embeddings with Homomorphism Counts](https://mlsanity.com/paper/2308.15283/) (2023)
- [The Complexity of Dynamic Least-Squares Regression](https://mlsanity.com/paper/2201.00228/) (2022)

## Abstract (arXiv)

The complexity of matrix multiplication is measured in terms of ω, the smallest real number such that two n× n matrices can be multiplied using O(nω+ε) field operations for all ε>0; the best bound until now is ω<2.37287 [Le Gall'14]. All bounds on ω since 1986 have been obtained using the so-called laser method, a way to lower-bound the `value' of a tensor in designing matrix multiplication algorithms. The main result of this paper is a refinement of the laser method that improves the resulting value bound for most sufficiently large tensors. Thus, even before computing any specific values, it is clear that we achieve an improved bound on ω, and we indeed obtain the best bound on ω to date: ω < 2.37286. The improvement is of the same magnitude as the improvement that [Le Gall'14] obtained over the previous bound [Vassilevska W.'12]. Our improvement to the laser method is quite general, and we believe it will have further applications in arithmetic complexity.