MathLabs

Open problem, Applied and computational mathematics, Algebra, posed 1969

Exponent of matrix multiplication ω\omega

Open

Let ω\omega denote the infimum of all real numbers τ\tau such that two n×nn \times n matrices over a field can be multiplied using O(nτ)O(n^\tau) arithmetic operations. Determine the exact value of ω\omega; in particular, is ω=2\omega = 2?

Research frontier as of 2026

As of 2026, the exact value of ω\omega remains open between 22 and 2.3711772.371177. The 2023–2024 breakthroughs by Duan, Wu, and Zhou and by Alman, Duan, Vassilevska Williams, Xu, Xu, and Zhou reduced ω\omega to 2.3713392.371339 via asymmetric combination loss analysis in the laser method, and a 2026 preprint by Dupont et al. pushed the level-44 optimization further to ω<2.371177\omega < 2.371177. However, barrier results show that the Coppersmith–Winograd tensor family cannot yield ω=2\omega = 2 on its own.

Best known results

  • Published laser-method refinements with asymmetric combination loss establish ω<2.371339\omega < 2.371339 (Alman, Duan, Vassilevska Williams, Xu, Xu, and Zhou 2024/2025), with a 2026 preprint by Dupont et al. certifying ω<2.371177\omega < 2.371177.
  • Ambainis, Filmus, and Le Gall (2015) proved that the laser method applied to powers of the Coppersmith–Winograd tensor cannot prove ω<2.3078\omega < 2.3078.

Tools and where they stop

ToolAchievedWhere it stops
Strassen's laser method and asymmetric combination loss analysisSuccessively lowered the upper bound on ω\omega from 2.4792.479 to 2.3711772.371177 by analyzing high tensor powers of the Coppersmith–Winograd tensorSubject to fundamental barriers (such as ω≥2.3078\omega \ge 2.3078 for the Coppersmith–Winograd family) and doubly exponential growth in optimization parameters with recursion level
Border rank and asymptotic sum inequalityConverts approximate decompositions of direct sums of matrix multiplication tensors into valid asymptotic upper bounds on ω\omegaRequires finding starting tensors of low border rank and high value, and no known family approaches ω=2\omega = 2

Open questions

  • Is ω=2\omega = 2, so that two n×nn \times n matrices can be multiplied in O(n2+ε)O(n^{2 + \varepsilon}) operations for every ε>0\varepsilon > 0?
  • Can any unconditional superlinear lower bound better than 2n22n^2 arithmetic operations be proved for general arithmetic circuits multiplying n×nn \times n matrices?

References

  1. Volker Strassen (1969). Gaussian elimination is not optimal · DOI:10.1007/BF02165411
  2. Don Coppersmith, Shmuel Winograd (1990). Matrix multiplication via arithmetic progressions · DOI:10.1016/S0747-7171(08)80013-2
  3. Ran Duan, Hongxun Wu, Renfei Zhou (2023). Faster Matrix Multiplication via Asymmetric Hashing · DOI:10.1109/FOCS57990.2023.00035 · arXiv:2210.10173
  4. Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei Zhou (2024). More Asymmetry Yields Faster Matrix Multiplication · arXiv:2404.16349