mlsanityData to 7 Oct 2026

More Asymmetry Yields Faster Matrix Multiplication

arXiv 2404.16349 ↗First posted 25 Apr 2024cs.DS cs.CCcited by 27

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 27 papers in the map (data through 7 Oct 2026). First posted on arXiv 25 Apr 2024.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 11; 2026: 13.

27 papers.

Sort:

  1. 2024A Tighter Complexity Analysis of SparseGPTcited by 19
  2. 2025Better Neural Network Expressivity: Subdividing the Simplexcited by 11
  3. 2024Fast John Ellipsoid Computation with Differential Privacy Optimizationcited by 7
  4. 2025Subquadratic Algorithms and Hardness for Attention with Any Temperaturecited by 4
  5. 2026Simple Projection-Free Algorithm for Contextual Recommendation with Logarithmic Regret and Robustnesscited by 4
  6. 2024Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimizationcited by 3
  7. 2025Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexitiescited by 2
  8. 2025Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structurecited by 2
  9. 2025A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimizationcited by 2
  10. 2025Graph Inference with Effective Resistance Queriescited by 1
  11. 2025Private Geometric Median in Nearly-Linear Timecited by 1
  12. 2026Sublinear Time Quantum Algorithm for Attention Approximationcited by 1
15 more
  1. 2026Towards Universal Convergence of Backward Error in Linear System Solverscited by 1
  2. 2026Improving the matrix multiplication exponent with modern optimization and AlphaEvolvecited by 1
  3. 2025The Morse Transform for Discrete Shape Analysiscited by 0
  4. 2025Resource Constrained Pathfinding with A* and Negative Weightscited by 0
  5. 2025Linear-Time Primitives for Algorithm Development in Graphical Causal Inferencecited by 0
  6. 2025Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Modelcited by 0
  7. 2026Reducing the Complexity of Matrix Multiplication by Quantum Computingcited by 0
  8. 2026Combinatorial Sparse PCA Beyond the Spiked Identity Modelcited by 0
  9. 2026On the Computational Hardness of Transformerscited by 0
  10. 2026LP-GEMM: Integrating Layout Propagation into GEMM Operationscited by 0
  11. 2026Accelerated Relax-and-Round for Concave Coverage Problemscited by 0
  12. 2026Approaching I/O-optimality for Approximate Attentioncited by 0
  13. 2026Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Modelcited by 0
  14. 2026Fast, Parallel, Query-Efficient Binary Classificationcited by 0
  15. 2026Efficient Dynamic Algorithms for Graph Neural Networks with Non-Linear Propagationcited by 0