mlsanityData to 7 Oct 2026

New Bounds for Matrix Multiplication: from Alpha to Omega

arXiv 2307.07970 ↗First posted 16 Jul 2023cs.DS cs.CCcited by 34

Not on the map. Why?

Abstract (arXiv)

The main contribution of this paper is a new improved variant of the laser method for designing matrix multiplication algorithms. Building upon the recent techniques of [Duan, Wu, Zhou, FOCS 2023], the new method introduces several new ingredients that not only yield an improved bound on the matrix multiplication exponent ω, but also improve the known bounds on rectangular matrix multiplication by [Le Gall and Urrutia, SODA 2018]. In particular, the new bound on ω is ω≤ 2.371552 (improved from ω≤ 2.371866). For the dual matrix multiplication exponent α defined as the largest α for which ω(1,α,1)=2, we obtain the improvement α ≥ 0.321334 (improved from α ≥ 0.31389). Similar improvements are obtained for various other exponents for multiplying rectangular matrices.

Key facts. Cited by 34 papers in the map (data through 7 Oct 2026). First posted on arXiv 16 Jul 2023.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 10; 2024: 12; 2025: 7; 2026: 5.

34 papers.

Sort:

  1. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  2. 2024A Tighter Complexity Analysis of SparseGPTcited by 19
  3. 2023Solving Dense Linear Systems Faster Than via Preconditioningcited by 12
  4. 2024Optimal Quantization for Matrix Multiplicationcited by 10
  5. 2024Testing Calibration in Nearly-Linear Timecited by 9
  6. 2023Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameterscited by 7
  7. 2024Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systemscited by 7
  8. 2024Fast John Ellipsoid Computation with Differential Privacy Optimizationcited by 7
  9. 2024The I/O Complexity of Attention, or How Optimal is Flash Attention?cited by 6
  10. 2024Truncated Variance Reduced Value Iterationcited by 6
  11. 2023Structured Semidefinite Programming for Recovering Structured Preconditionerscited by 5
  12. 2024Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioningcited by 4
22 more
  1. 2024Approximating Metric Magnitude of Point Setscited by 4
  2. 2024Second-Order Min-Max Optimization with Lazy Hessianscited by 4
  3. 2025The Structural Complexity of Matrix-Vector Multiplicationcited by 4
  4. 2024Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimizationcited by 3
  5. 2023Gradient Coding with Iterative Block Leverage Score Samplingcited by 2
  6. 2024Online Learning Of Expanding Graphscited by 2
  7. 2025Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structurecited by 2
  8. 2023Fast Minimization of Expected Logarithmic Loss via Stochastic Dual Averagingcited by 1
  9. 2023Polynomial-based Self-Attention for Table Representation learningcited by 1
  10. 2025TopInG: Topologically Interpretable Graph Learning via Persistent Rationale Filtrationcited by 1
  11. 2026Sublinear Time Quantum Algorithm for Attention Approximationcited by 1
  12. 2026The Generation-Recognition Asymmetry: Six Dimensions of a Fundamental Divide in Formal Language Theorycited by 1
  13. 2026Improving the matrix multiplication exponent with modern optimization and AlphaEvolvecited by 1
  14. 2023Iterative Sketching for Secure Coded Regressioncited by 0
  15. 2023ADMM Algorithms for Residual Network Training: Convergence Analysis and Parallel Implementationcited by 0
  16. 2023Accelerated Gradient Algorithms with Adaptive Subspace Search for Instance-Faster Optimizationcited by 0
  17. 2025Resource Constrained Pathfinding with A* and Negative Weightscited by 0
  18. 2025Temporal Robustness in Discrete Time Linear Dynamical Systemscited by 0
  19. 2025Linear cost mutual information estimation and independence test of similar performance as HSICcited by 0
  20. 2025Conditional Multidimensional Scaling with Incomplete Conditioning Datacited by 0
  21. 2026Reducing the Complexity of Matrix Multiplication by Quantum Computingcited by 0
  22. 2026Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Modelcited by 0