<p>Their phrase in that paper &quot;All work on matrix multiplication since 1986&quot; is...an oversimplification. While it's true that what they cite are all the papers that have improved the state of the art at the time, there has certainly been other work on matrix multiplication. This post will not be exhaustive either in terms of citations, but will at least point you towards the major directions I'm aware of (and probably by chasing citations forward/backward from these you can get everything).</p>
<p><strong>Other approaches.</strong> There have been other approaches to constructing algorithms for matrices of specific small sizes, and while these do not improve the state of the art bound on <span class="math-container">$\omega$</span>, they are still somewhat different methods that might someday do so. Examples include:</p>
<ul>
<li>Using symmetries to construct (or rule out) algorithms: <a href="https://arxiv.org/abs/1801.00843" rel="noreferrer">Ballard-Ikenmeyer-Landsberg-Ryder '18</a>, <a href="https://arxiv.org/abs/1612.01527" rel="noreferrer">G.-Moore '16</a>, <a href="https://arxiv.org/abs/1508.01110" rel="noreferrer">Burichenko '15</a>, <a href="https://arxiv.org/abs/2211.06485" rel="noreferrer">Burichenko '22</a></li>
<li>Using algorithmic searches to find new algorithms <a href="https://arxiv.org/abs/1108.2830" rel="noreferrer">Curtois-Bard-Hulme  '11</a> use a SAT solver, <a href="https://doi.org/10.1038/s41586-022-05172-4" rel="noreferrer">Fawzi et al. from Deepmind '22</a> uses reinforcement learning. We still don't understand the real &quot;why&quot; of most of these algorithms!</li>
</ul>
<p>I think there is value in trying to understand these methods and extend them to asymptotic results, but that is a personal opinion.</p>
<p><strong>Group-theoretic approach.</strong> As you say, there is also the group-theoretic approach of Cohn &amp; Umans (goes back actually to <a href="https://doi.org/10.1109/SFCS.2003.1238217" rel="noreferrer">their earlier FOCS '03 paper</a>). It is claimed in <a href="https://doi.org/10.1109/SFCS.2005.39" rel="noreferrer">the FOCS '05 paper</a> (and I believe) that all of the state of the art bounds at the time, although discovered by the laser method, can be reproduced by using Abelian groups in that method (even Abelian groups of bounded exponent, a technical point that will be important in the limitations below). I believe the same comment essentially applies to the state of the art bounds since then, though this has never been written down publicly. These is also a proposed extension of this approach using coherent configurations <a href="https://doi.org/10.1137/1.9781611973105.77" rel="noreferrer">Cohn-Umans SODA '13</a>, which introduces the potentially important notion of &quot;support rank&quot;.</p>
<p><strong>Limitations of group-theoretic approach.</strong> By extending the resolution of the Cap Set Conjecture, we showed (<a href="http://dx.doi.org/10.19086/da.1245" rel="noreferrer">Blasiak-Church-Cohn-G.-Nasland-Sawin-Umans, Discrete Analysis 2017</a>) that such constructions in Abelian groups of bounded exponent cannot achieve <span class="math-container">$\omega=2$</span> (though we do not give a precise bound like &quot;better than 2.1&quot;). We have even extended that &quot;barrier&quot; to many (but not all!) non-Abelian nilpotent groups that sitll have some parameters bounded (<a href="http://arxiv.org/abs/1712.02302" rel="noreferrer">Blasiak-Church-Cohn-G.-Umans arXiv '17</a>). In <a href="https://doi.org/10.4230/LIPIcs.ITCS.2023.19" rel="noreferrer">Blasiak-Cohn-G.-Pratt-Umans ITCS '23</a> we show that finite groups of Lie type can't work to get <span class="math-container">$\omega=2$</span> (and this covers most non-Abelian finite simple groups), but this bound is so specific it doesn't even rule out using direct products of non-Abelian finite simple groups. <a href="https://arxiv.org/abs/1702.00905" rel="noreferrer">Sawin '17</a> showed that for any finite group <span class="math-container">$G$</span>, using a family of constructions only in the powers <span class="math-container">$G^k$</span> cannot give <span class="math-container">$\omega=2$</span>. Some notable families that remain open are e.g. p-groups whose parameters escape the aforementioned bound from BCCGU, or families of quasi-simple or Fitting-trivial groups that avoid the bounds of BCGPU and Sawin. There are surely many more to explore!</p>
<p><strong>Some other refs.</strong>
<a href="https://arxiv.org/pdf/1811.11667.pdf" rel="noreferrer">Here is a nice 2-page survey by Landsberg</a> covering some developments between 2014-2018.</p>
<p><a href="https://arxiv.org/abs/1909.04785" rel="noreferrer">Connor-Gesmundo-Landsberg-Venture '19</a> rule out using the square or cube of the little Coppersmith-Winograd tensor to get further improvemnts.</p>

CC BY-SA 4.0
2024-02-09T17:12:25.623Z
Recent paper using a SAT solver to rule out 21-term decompositions for 3x3 matrix mult over Z/2Z with certain symmetries: https://arxiv.org/abs/2402.01011
Joshua Grochow
CC BY-SA 4.0
2024-02-03T00:19:47.483Z
2024-02-03T00:19:47.483Z
Joshua Grochow
<p>Let <span class="math-container">$\omega$</span> be the smallest constant so that we can do matrix multiplication in complexity <span class="math-container">$n^{\omega+o(1)}$</span>.</p>
<p>I am wondering what are the known avenues which establish the non-trivial bound <span class="math-container">$\omega&lt;3$</span>, and of these which have a known barrier that prevents one from achieving <span class="math-container">$\omega=2$</span>.</p>
<p>If there is too many avenues, I would appreciate some highlights, or some reference to learn more.</p>
<p><strong>Comments:</strong> In this paper (<a href="https://arxiv.org/abs/2307.07970" rel="nofollow noreferrer">https://arxiv.org/abs/2307.07970</a>), it is claimed that all work relies upon “the laser method” (or variants thereof), where it is impossible to show <span class="math-container">$\omega \le 2.3$</span>. However to my knowledge there is a different group-theoretic approach by Cohn et al. (<a href="https://arxiv.org/abs/math/0511460" rel="nofollow noreferrer">https://arxiv.org/abs/math/0511460</a>) with no known barrier.</p>
<p>I am hoping for clarification.</p>

CC BY-SA 4.0
2024-02-02T16:16:15.113Z
All you've mentioned is essentially correct. The past decade there's been an approach based on taking powers of a specific tensor. This handout by LeGall (2014) can show you the basics including the technique used http://francoislegall.com/LeGallISSAC14-tutorial-handout.pdf . The survey https://theoryofcomputing.org/articles/gs005/ (Bläser, 2013) provides a very detailed history of the methods used. The only restriction I am aware of is the one mentioned in the paper, the original work is https://arxiv.org/abs/1411.5414  . The best lower bound to date is https://arxiv.org/abs/1206.1530 afaik.
chazisop
<cc.complexity-theory><reference-request><matrices>
Approaches to fast matrix multiplication and their limits
Zach Hunter
# Approaches to fast matrix multiplication and their limits

(Asked by: username_0 on 2024-02-02)

Let $\omega$ be the smallest constant so that we can do matrix multiplication in complexity $n^{\omega+o(1)}$.

I am wondering what are the known avenues which establish the non-trivial bound $\omega<3$, and of these which have a known barrier that prevents one from achieving $\omega=2$.

If there is too many avenues, I would appreciate some highlights, or some reference to learn more.

**Comments:** In this paper (<https://arxiv.org/abs/2307.07970>), it is claimed that all work relies upon “the laser method” (or variants thereof), where it is impossible to show $\omega \le 2.3$. However to my knowledge there is a different group-theoretic approach by Cohn et al. (<https://arxiv.org/abs/math/0511460>) with no known barrier.

I am hoping for clarification.

**Tags:** cc.complexity-theory, reference-request, matrices

> **Comments:**
> **username_1**: All you've mentioned is essentially correct. The past decade there's been an approach based on taking powers of a specific tensor. This handout by LeGall (2014) can show you the basics including the technique used http://francoislegall.com/LeGallISSAC14-tutorial-handout.pdf . The survey https://theoryofcomputing.org/articles/gs005/ (Bläser, 2013) provides a very detailed history of the methods used. The only restriction I am aware of is the one mentioned in the paper, the original work is https://arxiv.org/abs/1411.5414  . The best lower bound to date is https://arxiv.org/abs/1206.1530 afaik.  

---

## 1 answers

### Answer by username_2 on 2024-02-03. Score: 7 | Accepted answer

Their phrase in that paper "All work on matrix multiplication since 1986" is...an oversimplification. While it's true that what they cite are all the papers that have improved the state of the art at the time, there has certainly been other work on matrix multiplication. This post will not be exhaustive either in terms of citations, but will at least point you towards the major directions I'm aware of (and probably by chasing citations forward/backward from these you can get everything).

**Other approaches.** There have been other approaches to constructing algorithms for matrices of specific small sizes, and while these do not improve the state of the art bound on $\omega$, they are still somewhat different methods that might someday do so. Examples include:

* Using symmetries to construct (or rule out) algorithms: [Ballard-Ikenmeyer-Landsberg-Ryder '18](https://arxiv.org/abs/1801.00843), [G.-Moore '16](https://arxiv.org/abs/1612.01527), [Burichenko '15](https://arxiv.org/abs/1508.01110), [Burichenko '22](https://arxiv.org/abs/2211.06485)
* Using algorithmic searches to find new algorithms [Curtois-Bard-Hulme '11](https://arxiv.org/abs/1108.2830) use a SAT solver, [Fawzi et al. from Deepmind '22](https://doi.org/10.1038/s41586-022-05172-4) uses reinforcement learning. We still don't understand the real "why" of most of these algorithms!

I think there is value in trying to understand these methods and extend them to asymptotic results, but that is a personal opinion.

**Group-theoretic approach.** As you say, there is also the group-theoretic approach of Cohn & Umans (goes back actually to [their earlier FOCS '03 paper](https://doi.org/10.1109/SFCS.2003.1238217)). It is claimed in [the FOCS '05 paper](https://doi.org/10.1109/SFCS.2005.39) (and I believe) that all of the state of the art bounds at the time, although discovered by the laser method, can be reproduced by using Abelian groups in that method (even Abelian groups of bounded exponent, a technical point that will be important in the limitations below). I believe the same comment essentially applies to the state of the art bounds since then, though this has never been written down publicly. These is also a proposed extension of this approach using coherent configurations [Cohn-Umans SODA '13](https://doi.org/10.1137/1.9781611973105.77), which introduces the potentially important notion of "support rank".

**Limitations of group-theoretic approach.** By extending the resolution of the Cap Set Conjecture, we showed ([Blasiak-Church-Cohn-G.-Nasland-Sawin-Umans, Discrete Analysis 2017](http://dx.doi.org/10.19086/da.1245)) that such constructions in Abelian groups of bounded exponent cannot achieve $\omega=2$ (though we do not give a precise bound like "better than 2.1"). We have even extended that "barrier" to many (but not all!) non-Abelian nilpotent groups that sitll have some parameters bounded ([Blasiak-Church-Cohn-G.-Umans arXiv '17](http://arxiv.org/abs/1712.02302)). In [Blasiak-Cohn-G.-Pratt-Umans ITCS '23](https://doi.org/10.4230/LIPIcs.ITCS.2023.19) we show that finite groups of Lie type can't work to get $\omega=2$ (and this covers most non-Abelian finite simple groups), but this bound is so specific it doesn't even rule out using direct products of non-Abelian finite simple groups. [Sawin '17](https://arxiv.org/abs/1702.00905) showed that for any finite group $G$, using a family of constructions only in the powers $G^k$ cannot give $\omega=2$. Some notable families that remain open are e.g. p-groups whose parameters escape the aforementioned bound from BCCGU, or families of quasi-simple or Fitting-trivial groups that avoid the bounds of BCGPU and Sawin. There are surely many more to explore!

**Some other refs.**
[Here is a nice 2-page survey by Landsberg](https://arxiv.org/pdf/1811.11667.pdf) covering some developments between 2014-2018.

[Connor-Gesmundo-Landsberg-Venture '19](https://arxiv.org/abs/1909.04785) rule out using the square or cube of the little Coppersmith-Winograd tensor to get further improvemnts.

> **Comments:**
> **username_2**: Recent paper using a SAT solver to rule out 21-term decompositions for 3x3 matrix mult over Z/2Z with certain symmetries: https://arxiv.org/abs/2402.01011  

---

