Is the exponent in the rectangular matrix multiplication convex?

Question

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

Answer 1

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

Answer 2

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