44
$\begingroup$

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.

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$?

Improve this question
$\endgroup$
1
  • $\begingroup$ In the newest version of this paper in arxiv.org/abs/1612.04208, the author claims to find an $O(n^2\log^c{n})$ algorithm for matrix multiplication. $\endgroup$
    – Mengfan Ma
    Commented Apr 22, 2021 at 9:28

3 Answers 3

Reset to default
32
$\begingroup$

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, "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.

Improve this answer
$\endgroup$
0
15
$\begingroup$

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))$.

Improve this answer
$\endgroup$
7
  • 3
    $\begingroup$ 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. $\endgroup$
    – JoshuaZ
    Commented Sep 11, 2019 at 11:34
  • 1
    $\begingroup$ @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})$. $\endgroup$
    – Joshua Grochow
    Commented Sep 11, 2019 at 15:34
  • 1
    $\begingroup$ @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?? $\endgroup$
    – Daniel Wagner
    Commented Sep 12, 2019 at 6:19
  • $\begingroup$ @JoshuaGrochow Doesn't fourier transform method of Cohn and Umans try to get $O(n^2poly(\log n))$ or is their goal different? $\endgroup$
    – Turbo
    Commented May 4, 2023 at 15:48
  • 1
    $\begingroup$ 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." $\endgroup$
    – Joshua Grochow
    Commented May 4, 2023 at 18:05
11
$\begingroup$

Josh Alman showed some cool lower bound results of MM, which won CCC 2019 best student paper award! http://drops.dagstuhl.de/opus/volltexte/2019/10834/pdf/LIPIcs-CCC-2019-12.pdf

Improve this answer
$\endgroup$
2
  • 7
    $\begingroup$ While this is definitely a really cool and interesting result, I don't really take it as evidence that MM can't be done in $O(n^2 poly(log n))$ time. It is evidence that the CW-style degeneration-of-high-tensor-power probably can't do that for you. But there are plenty of other possible constructions, e.g. by starting with a very different base tensor, or the Cohn-Umans group-theoretic approach (which can, in principle, produce infinite families of algorithms which are not just degenerations of high tensor powers of a starting one). $\endgroup$
    – Joshua Grochow
    Commented Sep 10, 2019 at 4:17
  • 4
    $\begingroup$ @JoshuaGrochow Thank you for pointing out this issue. $\endgroup$
    – user17918
    Commented Sep 10, 2019 at 4:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.