mlsanityData to 7 Oct 2026

Faster Matrix Multiplication via Asymmetric Hashing

arXiv 2210.10173 ↗First posted 18 Oct 2022cs.DScited by 19

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 8; 2024: 5; 2025: 1; 2026: 5.

19 papers.

Sort:

  1. 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31
  2. 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
  3. 2025Strassen Attention, Split VC Dimension and Compositionality in Transformerscited by 12
  4. 2024Optimal Quantization for Matrix Multiplicationcited by 10
  5. 2023Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameterscited by 7
  6. 2023Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Gamescited by 6
  7. 2023Convergence of Two-Layer Regression with Nonlinear Unitscited by 6
  8. 2024Arbitrary Polynomial Separations in Trainable Quantum Machine Learningcited by 5
  9. 2024Approximation and bounding techniques for the Fisher-Rao distances between parametric statistical modelscited by 2
  10. 2024Similarity and Dissimilarity Guided Co-association Matrix Construction for Ensemble Clusteringcited by 2
  11. 2023Multiparticle Kalman filter for object localization in symmetric environmentscited by 1
  12. 2023Inference for Probabilistic Dependency Graphscited by 1
7 more
  1. 2026Sublinear Time Quantum Algorithm for Attention Approximationcited by 1
  2. 2026Improving the matrix multiplication exponent with modern optimization and AlphaEvolvecited by 1
  3. 2023Efficiently-Verifiable Strong Uniquely Solvable Puzzles and Matrix Multiplicationcited by 0
  4. 2024Universal Matrix Multiplication on Quantum Computercited by 0
  5. 2026Reducing the Complexity of Matrix Multiplication by Quantum Computingcited by 0
  6. 2026Halpern Iteration Achieves tildeO(ε-1/p) pth-Order Oracle Complexity for Monotone Variational Inequalitiescited by 0
  7. 2026Optimal High-Order Methods for Solving Monotone Variational Inequalitiescited by 0