2
$\begingroup$

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.

$\endgroup$
1

1 Answer 1

7
$\begingroup$

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:

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). It is claimed in the FOCS '05 paper (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, 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) 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). In Blasiak-Cohn-G.-Pratt-Umans ITCS '23 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 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 covering some developments between 2014-2018.

Connor-Gesmundo-Landsberg-Venture '19 rule out using the square or cube of the little Coppersmith-Winograd tensor to get further improvemnts.

$\endgroup$
1
  • 1
    $\begingroup$ Recent paper using a SAT solver to rule out 21-term decompositions for 3x3 matrix mult over Z/2Z with certain symmetries: arxiv.org/abs/2402.01011 $\endgroup$ Feb 9 at 17:12

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.