<p>There is an analogy I use to justify the conjecture that $\omega = 2$ to myself.  I realize this is pretty heuristic, but nevertheless it has served me well, for example, in understanding some of the intuition behind the Cohn et al. paper.</p>

<p>Convolution and matrix multiplication are analogous.  If $A$ and $B$ are $n$-by-$n$ matrices and $C = AB$, then $C(i,j) = \sum_{k=1}^n A(i,k) B(k,j)$.  If $A$ and $B$ are $n$-length vectors and $C = A*B$, then $C(i) = \sum_{k=1}^n A(k)B(i-k)$.  In both cases, the final result is a vector consisting of sums of products, but the relational structure in the input data is different.  For convolution, we can use the FFT to compute the answer in $\tilde{O}(n)$ time instead of the trivial $O(n^2)$.  Analogously, one might expect an $\tilde{O}(n^2)$ time algorithm for matrix multiplication.  The question is: what is the analog of the Fourier transform which can help for matrix multiplication?</p>

CC BY-SA 2.5
2011-03-08T18:37:30.377Z
2011-03-08T18:37:30.377Z
arnab
<p>I don't know about others but I can tell you why I tend to believe that $\omega=2$. When you read through the history and development of fast matrix multiplication algorithms, I think that it is hard not to get feeling that all that we need is just a slightly better basic algorithm from which, even using known techniques, $\omega=2$ will follow. Basically, all algorithms today (including group theoretic ones) start with some "simple" construction that is then amplified. Those constructions are clever but they give the reader some sort of an "ad-hoc" feeling. I don't see a reason to believe that we cannot come up with better simple constructions. </p>

CC BY-SA 2.5
2011-03-08T15:05:20.623Z
2011-03-08T15:05:20.623Z
Amir Shpilka
<p>More likely that it is $O(n^{2} log(n^2))$. Having $\omega = 2$ seems fanciful as constant factor book-keeping doesn't seem like it could scale.</p>

CC BY-SA 3.0
2017-01-29T16:51:34.597Z
You misunderstand the definition of $\omega$: it is the infimum of all $c$ such that matrix multiplication can be solved in time $O(n^c)$. If there is a $O(n^2 \log^{10} n)$ matrix multiplication algorithm, this infimum will still be $2$. BTW there is a $\Omega(n^2\log n)$ bound in the model of arithmetic circuits with bounded coefficients.
Sasho Nikolov
CC BY-SA 3.0
2017-01-30T17:32:45.887Z
@SashoNikolov Thanks for pointing that out. Has anyone tried training a neural net for boolean matmul A*B=C?  [A entries, B entries, C entries] -> Bool (correct or incorrect multiply).  Curious what circuits the gradient decent/dropouts come up with; if trained circuits have attractors near prime decompositions. On 3x3, 4x4, 5x5, 6x6 it seems an hour of GPU would give some interesting results.
Chad Brewbaker
CC BY-SA 3.0
2017-01-29T08:24:46.790Z
2017-01-29T08:24:46.790Z
Chad Brewbaker
<p>I'd like to add to Mark Reitblatt's comment and Amir Shpilka's answer. First, one of the conjectures put forward by Cohn, Kleinberg, Szegedy, and Umans is not group-theoretic but is purely combinatorial (Conj. 3.4 in <a href="http://dx.doi.org/10.1109/SFCS.2005.39">their FOCS '05 paper</a>). This conjecture says that the "strong USP capacity is $\frac{3}{2^{2/3}}$." Coppersmith and Winograd, in exhibiting their currently-best algorithm for matrix multiplication, showed that the USP capacity is this same number $\frac{3}{2^{2/3}}$ (although they did not phrase it quite this way). Although there is a difference between strong USPs and USPs, this is some evidence that their conjecture is at least plausible.</p>

<p>(For their other Conjecture 4.7, which is group-theoretic, I do not know of any similar evidence of plausibility, beyond just intuition.)</p>

<p>Second, I agree with Amir Shpilka that the string of past algorithms has a somewhat ad-hoc feel. However, one of the nice things about the group-theoretic approach is that almost all (not quite all) of the previous algorithms can be phrased in this approach. Although the various group-theoretic constructions in [CKSU] may seem a little ad-hoc on the outside, within the context of the group-theoretic framework they appear significantly more natural and less ad-hoc (at least to me) than many of the previous algorithms.</p>

CC BY-SA 3.0
2013-10-18T02:11:28.793Z
When I think about Capacity I think about independent sets and cliques. What is the dictionary between USPs and the explicit construction of the underlying graph and is there a structure to these graphs?
Turbo
CC BY-SA 4.0
2022-05-10T11:53:20.890Z
Would this answer need an update since 10 years have passed and some no go results have been obtained?
Turbo
CC BY-SA 2.5
2011-03-08T16:04:28.807Z
2011-03-08T20:03:17.873Z
2011-03-08T20:03:17.873Z
Joshua Grochow
<p>It is widely conjectured that $\omega$, the optimal exponent for matrix multiplication, is in fact equal to 2. My question is simple: </p>

<blockquote>
  <p>What reasons do we have for believing that $\omega = 2$?</p>
</blockquote>

<p>I'm aware of fast algorithms like Coppersmith-Winograd, but I don't know why these might be considered evidence for $\omega = 2$.</p>

<p>Naively, it seems to me like a classic example where a community just hopes that a result is true purely for aesthetic reasons. I would love to know if that's essentially the case here.</p>

CC BY-SA 2.5
2011-03-08T05:04:19.223Z
I suspect the answer is largely aesthetics, and the lack of a good reason for it to be larger than 2. There was a paper in FOCS '05 that gave some group theoretic constructions for matrix mult that matched the current known exponents and also gave 2 group theoretic conjectures which imply $\omega=2$. [PDF](http://www.cs.cornell.edu/~rdk/papers/CKSU05.pdf)
Mark Reitblatt
CC BY-SA 2.5
2011-03-08T05:20:10.563Z
A few years ago, I had a conversation with Strassen where he said he believed $\omega > 2$. I am not sure what were his reasons, though.
Ryan Williams
CC BY-SA 2.5
2011-03-08T06:14:02.443Z
@Mark, Yes, I know about the group theoretic approach, but I still don't know why the group theory conjectures are considered believable if that is indeed the case.
Steve Flammia
CC BY-SA 2.5
2011-03-08T06:14:43.207Z
@Ryan, let's hope that Strassen reads cstheory.stackexchange. :)
Steve Flammia
CC BY-SA 2.5
2011-03-08T09:51:11.493Z
There is a $\Omega(n\log n)$ lower bound (under some restrictions) due to Ran Raz, so a better conjecture would be that $\omega = 2$ is not achieved (but the infimum is indeed $2$).
Yuval Filmus
CC BY-SA 2.5
2011-03-08T16:44:43.483Z
@Yuval, yes, you are correct of course. I was being a bit informal to say $\omega=2$.
Steve Flammia
CC BY-SA 2.5
2011-03-09T05:49:08.737Z
@Yuval, @Steve: 1) $\omega$ is usually *defined* as a limit. 2) We already know that whatever $\omega$ is, it is not achieved (it is an inf and not a min). See this Coppersmith-Winograd paper: http://dx.doi.org/10.1137/0211038. From the abstract: "the exponent for matrix multiplication is a limit point, that is, it cannot be realized by any single algorithm." (Given the details of their results, I think this statement cannot quite be taken naively at face value, but this is mostly a technicality.)
Joshua Grochow
CC BY-SA 4.0
2022-10-06T09:05:19.590Z
I noticed that in [Deepmind's paper](https://www.nature.com/articles/s41586-022-05172-4) they claimed an asymptomatic complexity of $log_n(R)$ which can be far lower than 2 or even one for large matrices of small ranks.
Aditya P
<ds.algorithms><linear-algebra><matrix-product>
Evidence that matrix multiplication can be done in quadratic time?
Steve Flammia
# Evidence that matrix multiplication can be done in quadratic time?

(Asked by: username_0 on 2011-03-08)

It is widely conjectured that $\omega$, the optimal exponent for matrix multiplication, is in fact equal to 2. My question is simple:

> What reasons do we have for believing that $\omega = 2$?

I'm aware of fast algorithms like Coppersmith-Winograd, but I don't know why these might be considered evidence for $\omega = 2$.

Naively, it seems to me like a classic example where a community just hopes that a result is true purely for aesthetic reasons. I would love to know if that's essentially the case here.

**Tags:** ds.algorithms, linear-algebra, matrix-product

> **Comments:**
> **username_1**: I suspect the answer is largely aesthetics, and the lack of a good reason for it to be larger than 2. There was a paper in FOCS '05 that gave some group theoretic constructions for matrix mult that matched the current known exponents and also gave 2 group theoretic conjectures which imply $\omega=2$. [PDF](http://www.cs.cornell.edu/~rdk/papers/CKSU05.pdf)  
> **username_2**: A few years ago, I had a conversation with Strassen where he said he believed $\omega > 2$. I am not sure what were his reasons, though.  
> **username_0**: @Mark, Yes, I know about the group theoretic approach, but I still don't know why the group theory conjectures are considered believable if that is indeed the case.  
> **username_0**: @Ryan, let's hope that Strassen reads cstheory.stackexchange. :)  
> **username_3**: There is a $\Omega(n\log n)$ lower bound (under some restrictions) due to Ran Raz, so a better conjecture would be that $\omega = 2$ is not achieved (but the infimum is indeed $2$).  
> **username_0**: @Yuval, yes, you are correct of course. I was being a bit informal to say $\omega=2$.  
> **username_4**: @Yuval, @Steve: 1) $\omega$ is usually *defined* as a limit. 2) We already know that whatever $\omega$ is, it is not achieved (it is an inf and not a min). See this Coppersmith-Winograd paper: http://dx.doi.org/10.1137/0211038. From the abstract: "the exponent for matrix multiplication is a limit point, that is, it cannot be realized by any single algorithm." (Given the details of their results, I think this statement cannot quite be taken naively at face value, but this is mostly a technicality.)  
> **username_5**: I noticed that in [Deepmind's paper](https://www.nature.com/articles/s41586-022-05172-4) they claimed an asymptomatic complexity of $log_n(R)$ which can be far lower than 2 or even one for large matrices of small ranks.  

---

## 4 answers

### Answer by username_4 on 2011-03-08. Score: 20 | Accepted answer

I'd like to add to username_1's comment and username_7's answer. First, one of the conjectures put forward by Cohn, Kleinberg, Szegedy, and Umans is not group-theoretic but is purely combinatorial (Conj. 3.4 in [their FOCS '05 paper](http://dx.doi.org/10.1109/SFCS.2005.39)). This conjecture says that the "strong USP capacity is $\frac{3}{2^{2/3}}$." Coppersmith and Winograd, in exhibiting their currently-best algorithm for matrix multiplication, showed that the USP capacity is this same number $\frac{3}{2^{2/3}}$ (although they did not phrase it quite this way). Although there is a difference between strong USPs and USPs, this is some evidence that their conjecture is at least plausible.

(For their other Conjecture 4.7, which is group-theoretic, I do not know of any similar evidence of plausibility, beyond just intuition.)

Second, I agree with username_7 that the string of past algorithms has a somewhat ad-hoc feel. However, one of the nice things about the group-theoretic approach is that almost all (not quite all) of the previous algorithms can be phrased in this approach. Although the various group-theoretic constructions in [CKSU] may seem a little ad-hoc on the outside, within the context of the group-theoretic framework they appear significantly more natural and less ad-hoc (at least to me) than many of the previous algorithms.

> **Comments:**
> **username_10**: When I think about Capacity I think about independent sets and cliques. What is the dictionary between USPs and the explicit construction of the underlying graph and is there a structure to these graphs?  
> **username_10**: Would this answer need an update since 10 years have passed and some no go results have been obtained?  

---

### Answer by username_7 on 2011-03-08. Score: 28

I don't know about others but I can tell you why I tend to believe that $\omega=2$. When you read through the history and development of fast matrix multiplication algorithms, I think that it is hard not to get feeling that all that we need is just a slightly better basic algorithm from which, even using known techniques, $\omega=2$ will follow. Basically, all algorithms today (including group theoretic ones) start with some "simple" construction that is then amplified. Those constructions are clever but they give the reader some sort of an "ad-hoc" feeling. I don't see a reason to believe that we cannot come up with better simple constructions.


---

### Answer by username_6 on 2011-03-08. Score: 21

There is an analogy I use to justify the conjecture that $\omega = 2$ to myself. I realize this is pretty heuristic, but nevertheless it has served me well, for example, in understanding some of the intuition behind the Cohn et al. paper.

Convolution and matrix multiplication are analogous. If $A$ and $B$ are $n$-by-$n$ matrices and $C = AB$, then $C(i,j) = \sum\_{k=1}^n A(i,k) B(k,j)$. If $A$ and $B$ are $n$-length vectors and $C = A\*B$, then $C(i) = \sum\_{k=1}^n A(k)B(i-k)$. In both cases, the final result is a vector consisting of sums of products, but the relational structure in the input data is different. For convolution, we can use the FFT to compute the answer in $\tilde{O}(n)$ time instead of the trivial $O(n^2)$. Analogously, one might expect an $\tilde{O}(n^2)$ time algorithm for matrix multiplication. The question is: what is the analog of the Fourier transform which can help for matrix multiplication?


---

### Answer by username_8 on 2017-01-29. Score: -1

More likely that it is $O(n^{2} log(n^2))$. Having $\omega = 2$ seems fanciful as constant factor book-keeping doesn't seem like it could scale.

> **Comments:**
> **username_9**: You misunderstand the definition of $\omega$: it is the infimum of all $c$ such that matrix multiplication can be solved in time $O(n^c)$. If there is a $O(n^2 \log^{10} n)$ matrix multiplication algorithm, this infimum will still be $2$. BTW there is a $\Omega(n^2\log n)$ bound in the model of arithmetic circuits with bounded coefficients.  
> **username_8**: @SashoNikolov Thanks for pointing that out. Has anyone tried training a neural net for boolean matmul A*B=C?  [A entries, B entries, C entries] -> Bool (correct or incorrect multiply).  Curious what circuits the gradient decent/dropouts come up with; if trained circuits have attractors near prime decompositions. On 3x3, 4x4, 5x5, 6x6 it seems an hour of GPU would give some interesting results.  

---

