32 votes

Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time

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 ...
Josh Alman's user avatar
15 votes

Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time

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 ...
Joshua Grochow's user avatar
5 votes
Accepted

Fast Finding Main Diagonal of Matrix Multiplication

Not unless $\omega = 2$. Take $B = \operatorname{id}$, $A = \begin{bmatrix}X & Y\end{bmatrix}$. You can extract $XY$ from $A^TBA$. UPDATE: I missed the main diagonal part of the question. Even ...
Vladimir Lysikov's user avatar
4 votes
Accepted

Low-depth arithmetic complexity of the product of $k$ matrices

I am not sure about specifically depth-three lower bounds, but there has been a lot of depth-4 (and 5) lower bounds, usually assuming other constraints as well. For instance (and without any claim of ...
Bruno's user avatar
  • 4,504
4 votes

Bigger picture behind the choice of matrices in the Strassen algorithm

Several authors have attempted to elucidate the structure of Strassen's algorithm. The two most recent I am aware of are: Ikenmeyer and Lysikov '17 give a beautiful exposition, though ultimately the ...
Joshua Grochow's user avatar
4 votes
Accepted

Is the exponent in the rectangular matrix multiplication convex?

Does Lemma 3.6 of https://arxiv.org/abs/2009.10217 answer your original question of convexity of the matrix multiplication constant?
walkerbacker's user avatar
2 votes

Is the exponent in the rectangular matrix multiplication convex?

I found an answer in the paper "Fast sparse matrix multiplication" as Theorem 2.4. The authors cite "Fast rectangular matrix multiplications and applications", so that's the ...
user2316602's user avatar
2 votes

Face-splitting product of two Vandermonde matrices: When is is invertible?

Sorry if I am missing something, but isn't it always singular in your special case? The first column is identically $1$, the second column is $(\beta_1,\ldots,\beta_{n^2})^T$, and the $n+1$'th column ...
Jason Gaitonde's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible