33
$\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 exists an $O(n^2 \log^k n)$ algorithm 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?

$\endgroup$
27
$\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.

$\endgroup$
11
$\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 crazy 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))$.

$\endgroup$
  • 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 Sep 11 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 Sep 11 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 Sep 12 at 6:19
8
$\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

$\endgroup$
  • 5
    $\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 Sep 10 at 4:17
  • 3
    $\begingroup$ @JoshuaGrochow Thank you for pointing out this issue. $\endgroup$ – Rupei Xu Sep 10 at 4:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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