# Is the exponent in the rectangular matrix multiplication convex?

My question is regarding the paper "Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor". In the paper, the authors show an algorithm for multiplying a $$n \times n^c$$ and a $$n^c \times n$$ matrix. The authors show a graph of how the exponent in the time complexity depends on $$c$$. This graph is clearly convex. This would mean that one can upper bound the time complexity by linearly interpolating the exponent between that case of $$c = 0.31389$$ (where the exponent is 2) and $$c=1$$ (where the exponent is $$\omega$$). This would be useful for stating the time complexity of an algorithm I came up with.

However, they do not prove that the graph is convex. Is it convex? If so, any ideas as to how to cite this fact?

https://arxiv.org/abs/1708.05622

## 2 Answers

Does Lemma 3.6 of https://arxiv.org/abs/2009.10217 answer your original question of convexity of the matrix multiplication constant?

• It does! That is exactly what I was looking for! Feb 27 at 14:48

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 original source, I guess. It is possible to do it in a black-box fashion, so it works for any fast multiplication algorithms. That, of course, does not prove convexity but it does allow to upper-bound the exponent, as I needed.

https://www.cs.tau.ac.il/~zwick/papers/sparse.pdf

• Can you clarify in the answer what exactly says the statement that you found in that paper? Feb 25 at 13:41
• I have added a link to make it easier for people to find the statement. It is written better than I can do it, so I think it is best read in the paper :-) Feb 25 at 13:44
• @user2316602 The problem is that links go stale; this is a fine answer right now but might not be next year or two years from now. It's best to make answers self-contained if you're relying on anything with any more net volatility than, say, Wikipedia. Feb 25 at 17:37