Using a naive lower bound and schoolbook matrix multiplication for the upper bound, one can straightforwardly conclude that {{math|2 ≤ ω ≤ 3}}. Whether {{math|1=ω = 2}} is a major open question in [[theoretical computer science]], and there is a line of research developing matrix multiplication algorithms to get improved bounds on {{math|ω}}.
The currentpreviously best bound on {{math|ω}} is {{math|ω < 2.3728596}}, by Josh Alman and [[Virginia Vassilevska Williams]].<ref name="aw20"/> This algorithm, like all other recent algorithms in this line of research, uses the ''laser method'', a generalization of the Coppersmith–Winograd algorithm, which was given by [[Don Coppersmith]] and [[Shmuel Winograd]] in 1990 and was the best matrix multiplication algorithm until 2010.<ref name="coppersmith">{{Citation|doi=10.1016/S0747-7171(08)80013-2 |title=Matrix multiplication via arithmetic progressions |url=http://www.cs.umd.edu/~gasarch/TOPICS/ramsey/matrixmult.pdf |year=1990 |last1=Coppersmith |first1=Don |last2=Winograd |first2=Shmuel |journal=Journal of Symbolic Computation |volume=9|issue=3|pages=251|doi-access=free }}</ref> The conceptual idea of these algorithms are similar to Strassen's algorithm: a way is devised for multiplying two {{math|''k'' × ''k''}}-matrices with fewer than {{math|''k''<sup>3</sup>}} multiplications, and this technique is applied recursively. The laser method has limitations to its power, and cannot be used to show that {{math|ω < 2.3725}}.<ref name="afl14">{{Cite journal|last1=Ambainis|first1=Andris|last2=Filmus|first2=Yuval|last3=Le Gall|first3=François|date=2015-06-14|title=Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method|url=https://doi.org/10.1145/2746539.2746554|journal=Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing|series=STOC '15|___location=Portland, Oregon, USA|publisher=Association for Computing Machinery|pages=585–593|doi=10.1145/2746539.2746554|arxiv=1411.5414 |isbn=978-1-4503-3536-2|s2cid=8332797 }}</ref> Duan, Wu and Zhou identify a source of potential optimization in the laser method termed ''combination loss''. They find a way to exploit this to devise a variant of the laser method which they use to show {{math|ω < 2.37188}} breaking the barrier for any conventional laser method algorithm. With this newer approach annother bound<ref name="afl14"/> applies according to Duan, Wu and Zhou and showing {{math|ω < 2.3078}} will not be possible only adressing combination loss in the laser method.
=== Group theory reformulation of matrix multiplication algorithms ===
Line 250 ⟶ 252:
=== Lower bounds for ω ===
There is a trivial lower bound of {{tmath|\omega \ge 2}}. Since any algorithm for multiplying two {{math|''n'' × ''n''}}-matrices has to process all {{math|2''n''<sup>2</sup>}} entries, there is a trivial asymptotic lower bound of {{math|Ω(''n''<sup>2</sup>)}} operations for any matrix multiplication algorithm. Thus {{tmath|2\le \omega < 2.37337188}}. It is unknown whether {{tmath|\omega > 2}}. The best known lower bound for matrix-multiplication complexity is {{math|Ω(''n''<sup>2</sup> log(''n''))}}, for bounded coefficient [[Arithmetic circuit complexity|arithmetic circuits]] over the real or complex numbers, and is due to [[Ran Raz]].<ref>{{cite journal | last1 = Raz | first1 = Ran | author-link = Ran Raz | year = 2002| title = On the complexity of matrix product | journal = Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing | pages = 144 | doi = 10.1145/509907.509932 | isbn = 1581134959 | s2cid = 9582328 }}</ref>
