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?



2 Answers 2


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

  • 1
    $\begingroup$ It does! That is exactly what I was looking for! $\endgroup$ Commented Feb 27, 2021 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.


  • $\begingroup$ Can you clarify in the answer what exactly says the statement that you found in that paper? $\endgroup$ Commented Feb 25, 2021 at 13:41
  • $\begingroup$ 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 :-) $\endgroup$ Commented Feb 25, 2021 at 13:44
  • 2
    $\begingroup$ @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. $\endgroup$ Commented Feb 25, 2021 at 17:37

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.