# Tag Info

### 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 ...

### 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 ...
Accepted

### Matrix multiplication with transpose

No. Consider block matrices $A = \left(\begin{matrix} 0 & 0 \\ 0 & X \end{matrix}\right)$ (with symmetric $X$) and $B = \left(\begin{matrix} 0 & Y \\ 0 & 0 \end{matrix} \right)$. ...
Accepted

### Arithmetic complexity of matrix powering

It depends on the relationship between $m$ and $d$. If $m \geq 3$ is fixed, but $d$ is allowed to grow without bound, then the corresponding class of functions is exactly the same as functions with ...
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 ...
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?
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 ...

### 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 ...
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 ...
Because $\mathbf{c}' = R'\mathbf{p}$ and $R'$ contains 3 nonzero elements in each row.