<p>There's an algorithm for multiplying an <span class="math-container">$N \times N^{0.172}$</span> matrix with an <span class="math-container">$N^{0.172} \times N$</span> matrix in <span class="math-container">$N^2 \operatorname{polylog}\left(N\right)$</span> arithmetic operations. The main identity used for it comes from Coppersmith's paper "Rapid multiplication of rectangular matrices", but the explanation for why it leads to <span class="math-container">$N^2 \operatorname{polylog}\left(N\right)$</span> instead of <span class="math-container">$N^{2 + \epsilon}$</span> is in the appendix of Williams' <a href="https://arxiv.org/abs/1401.2444" rel="noreferrer">paper</a>, "New algorithms and lower bounds for circuits with linear threshold gates".</p>

<p>This only works because Coppersmith's identity has some additional structure you can take advantage of, and the more recent MM algorithms don't seem to have this structure. That said, I'm not sure why one can't hope to extend this approach to <span class="math-container">$N \times N \times N$</span> matrix multiplication.</p>

CC BY-SA 4.0
2019-09-10T15:46:55.920Z
2019-09-12T04:52:22.313Z
2019-09-12T04:52:22.313Z
Josh Alman
<p>Well, one thing is I think that all the constructions we know of - and even the families of potential constructions that people have proposed (e.g., Cohn-Umans approaches, generalizations of Coppersmith-Winograd) - would &quot;simply&quot; produce a family of algorithms <span class="math-container">$A_\epsilon$</span> running in time <span class="math-container">$O(n^{2+\epsilon})$</span>. So to have a single algorithm which ran in <span class="math-container">$O(n^2 poly(\log n))$</span>, it would have to not just be way asymptotically better than current approaches, but would have to look <em>really</em> different.</p>
<p>Big caveat: I think. I've never really thought too hard about how much one would have to modify/add to the existing approaches so that they could plausibly produce a single algorithm running in time <span class="math-container">$O(n^2 poly(\log n))$</span>.</p>

CC BY-SA 4.0
2019-09-11T11:34:35.467Z
I'm not sure how having a family doesn't plausibly lead to O(n^2poly(log n)) since if one could describe the family well enough then one could choose more and more efficient members of the family for larger n. The only reason then that this isn't plausibly O(n^2poly(log N)) is that the constants involved would probably be very large, but it isn't obvious that that's necessarily the case.
JoshuaZ
CC BY-SA 4.0
2019-09-11T15:34:27.643Z
@JoshuaZ: In principle it doesn't; in practice, each member of the family that arises from these approaches produces an algorithm with running time $O(n^{2+x})$, and the idea of most of the approaches is simply that you have a family such that, for any $\varepsilon > 0$, there is a member of the family resulting in an algorithm with runtime $O(n^{2+\varepsilon})$.
Joshua Grochow
CC BY-SA 4.0
2019-09-12T06:19:40.453Z
@JoshuaZ I suppose another even weirder way it could fail would be if somehow choosing/constructing a family member took more than O(n^2 poly(log n)) time -- e.g. perhaps O(1/e) code is needed to implement the O(n^(2+e)) algorithm or something. Wouldn't that be wild??
Daniel Wagner
CC BY-SA 4.0
2023-05-04T15:48:44.307Z
@JoshuaGrochow Doesn't fourier transform method of Cohn and Umans try to get $O(n^2poly(\log n))$ or is their goal different?
Turbo
CC BY-SA 4.0
2023-05-04T16:01:34.847Z
@Turbo: I included the Cohn-Umans approach in my list of things that would produce $O(n^{2+\varepsilon})$.
Joshua Grochow
CC BY-SA 4.0
2023-05-04T17:58:11.483Z
@JoshuaGrochow Is $\epsilon>0$ fixed or has some other meaning in Cohn-Umans approach?
Turbo
CC BY-SA 4.0
2023-05-04T18:05:04.270Z
The goal (and what would be produced by many of these techniques) is "for all $\varepsilon > 0$, there exists an algorithm running in $O(n^{2+\varepsilon})$ time."
Joshua Grochow
CC BY-SA 4.0
2019-09-10T05:12:22.133Z
2023-05-03T02:54:23.213Z
2023-05-03T02:54:23.213Z
Joshua Grochow
<p>It is commonly believed that for all <span class="math-container">$\epsilon &gt; 0$</span>, it is possible to multiply two <span class="math-container">$n \times n$</span> matrices in <span class="math-container">$O(n^{2 + \epsilon})$</span> time. Some discussion is <a href="https://cstheory.stackexchange.com/questions/5341/evidence-that-matrix-multiplication-can-be-done-in-quadratic-time">here</a>.</p>

<p>I have asked some people who are more familiar with the research whether they think that there is a <span class="math-container">$k&gt;0$</span> independent of <span class="math-container">$n$</span> such that there exists an <span class="math-container">$O(n^2 \log^k n)$</span> algorithm for matrix multiplication and they overwhelmingly seemed to have intuition that the answer is "no" but could not explain why. That is, they believe that we can do it in <span class="math-container">$O(n^{2.001})$</span> time, but not <span class="math-container">$O(n^2 \log^{100} n)$</span> time.</p>

<p>What reasons are there to believe that there is no <span class="math-container">$O(n^2 \log^k n)$</span> algorithm at a fixed <span class="math-container">$k&gt;0$</span>?</p>

CC BY-SA 4.0
2021-04-22T09:28:37.963Z
In the newest version of this paper in https://arxiv.org/abs/1612.04208, the author claims to find an $O(n^2\log^c{n})$ algorithm for matrix multiplication.
Mengfan Ma
<cc.complexity-theory><linear-algebra><big-picture><matrices><matrix-product>
Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time
Brian
# Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time

(Asked by: username_0 on 2019-09-09)

It is commonly believed that for all $\epsilon > 0$, it is possible to multiply two $n \times n$ matrices in $O(n^{2 + \epsilon})$ time. Some discussion is [here](https://cstheory.stackexchange.com/questions/5341/evidence-that-matrix-multiplication-can-be-done-in-quadratic-time).

I have asked some people who are more familiar with the research whether they think that there is a $k>0$ independent of $n$ such that there exists an $O(n^2 \log^k n)$ algorithm for matrix multiplication and they overwhelmingly seemed to have intuition that the answer is "no" but could not explain why. That is, they believe that we can do it in $O(n^{2.001})$ time, but not $O(n^2 \log^{100} n)$ time.

What reasons are there to believe that there is no $O(n^2 \log^k n)$ algorithm at a fixed $k>0$?

**Tags:** cc.complexity-theory, linear-algebra, big-picture, matrices, matrix-product

> **Comments:**
> **username_1**: In the newest version of this paper in https://arxiv.org/abs/1612.04208, the author claims to find an $O(n^2\log^c{n})$ algorithm for matrix multiplication.  

---

## 2 answers

### Answer by username_2 on 2019-09-10. Score: 31

There's an algorithm for multiplying an $N \times N^{0.172}$ matrix with an $N^{0.172} \times N$ matrix in $N^2 \operatorname{polylog}\left(N\right)$ arithmetic operations. The main identity used for it comes from Coppersmith's paper "Rapid multiplication of rectangular matrices", but the explanation for why it leads to $N^2 \operatorname{polylog}\left(N\right)$ instead of $N^{2 + \epsilon}$ is in the appendix of Williams' [paper](https://arxiv.org/abs/1401.2444), "New algorithms and lower bounds for circuits with linear threshold gates".

This only works because Coppersmith's identity has some additional structure you can take advantage of, and the more recent MM algorithms don't seem to have this structure. That said, I'm not sure why one can't hope to extend this approach to $N \times N \times N$ matrix multiplication.


---

### Answer by username_3 on 2019-09-10. Score: 15

Well, one thing is I think that all the constructions we know of - and even the families of potential constructions that people have proposed (e.g., Cohn-Umans approaches, generalizations of Coppersmith-Winograd) - would "simply" produce a family of algorithms $A\_\epsilon$ running in time $O(n^{2+\epsilon})$. So to have a single algorithm which ran in $O(n^2 poly(\log n))$, it would have to not just be way asymptotically better than current approaches, but would have to look *really* different.

Big caveat: I think. I've never really thought too hard about how much one would have to modify/add to the existing approaches so that they could plausibly produce a single algorithm running in time $O(n^2 poly(\log n))$.

> **Comments:**
> **username_4**: I'm not sure how having a family doesn't plausibly lead to O(n^2poly(log n)) since if one could describe the family well enough then one could choose more and more efficient members of the family for larger n. The only reason then that this isn't plausibly O(n^2poly(log N)) is that the constants involved would probably be very large, but it isn't obvious that that's necessarily the case.  
> **username_3**: @username_4: In principle it doesn't; in practice, each member of the family that arises from these approaches produces an algorithm with running time $O(n^{2+x})$, and the idea of most of the approaches is simply that you have a family such that, for any $\varepsilon > 0$, there is a member of the family resulting in an algorithm with runtime $O(n^{2+\varepsilon})$.  
> **username_5**: @username_4 I suppose another even weirder way it could fail would be if somehow choosing/constructing a family member took more than O(n^2 poly(log n)) time -- e.g. perhaps O(1/e) code is needed to implement the O(n^(2+e)) algorithm or something. Wouldn't that be wild??  
> **username_6**: @JoshuaGrochow Doesn't fourier transform method of Cohn and Umans try to get $O(n^2poly(\log n))$ or is their goal different?  
> **username_3**: @username_6: I included the Cohn-Umans approach in my list of things that would produce $O(n^{2+\varepsilon})$.  
> **username_6**: @JoshuaGrochow Is $\epsilon>0$ fixed or has some other meaning in Cohn-Umans approach?  
> **username_3**: The goal (and what would be produced by many of these techniques) is "for all $\varepsilon > 0$, there exists an algorithm running in $O(n^{2+\varepsilon})$ time."  

---

