<p>Does Lemma 3.6 of <a href="https://arxiv.org/abs/2009.10217" rel="nofollow noreferrer">https://arxiv.org/abs/2009.10217</a> answer your original question of convexity of the matrix multiplication constant?</p>

CC BY-SA 4.0
2021-02-27T14:48:07.697Z
It does! That is exactly what I was looking for!
user2316602
CC BY-SA 4.0
2021-02-27T14:02:04.193Z
2021-02-27T15:58:11.660Z
2021-02-27T15:58:11.660Z
walkerbacker
<p>I found an answer in the paper &quot;Fast sparse matrix multiplication&quot; as Theorem 2.4. The authors cite &quot;Fast rectangular matrix multiplications and applications&quot;, 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.</p>
<p><a href="https://www.cs.tau.ac.il/%7Ezwick/papers/sparse.pdf" rel="nofollow noreferrer">https://www.cs.tau.ac.il/~zwick/papers/sparse.pdf</a></p>

CC BY-SA 4.0
2021-02-25T13:41:16.953Z
Can you clarify in the answer what exactly says the statement that you found in that paper?
Emil Jeřábek
CC BY-SA 4.0
2021-02-25T13:44:48.980Z
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 :-)
user2316602
CC BY-SA 4.0
2021-02-25T17:37:36.037Z
@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.
Steven Stadnicki
CC BY-SA 4.0
2021-02-25T12:31:52.057Z
2021-02-25T13:43:13.277Z
2021-02-25T13:43:13.277Z
user2316602
<p>My question is regarding the paper &quot;Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor&quot;. In the paper, the authors show an algorithm for multiplying a <span class="math-container">$n \times n^c$</span> and a <span class="math-container">$n^c \times n$</span> matrix. The authors show a graph of how the exponent in the time complexity depends on <span class="math-container">$c$</span>. 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 <span class="math-container">$c = 0.31389$</span> (where the exponent is 2) and <span class="math-container">$c=1$</span> (where the exponent is <span class="math-container">$\omega$</span>). This would be useful for stating the time complexity of an algorithm I came up with.</p>
<p>However, they do not prove that the graph is convex. Is it convex? If so, any ideas as to how to cite this fact?</p>
<p><a href="https://arxiv.org/abs/1708.05622" rel="noreferrer">https://arxiv.org/abs/1708.05622</a></p>

<ds.algorithms><time-complexity><matrix-product>
Is the exponent in the rectangular matrix multiplication convex?
user2316602
# Is the exponent in the rectangular matrix multiplication convex?

(Asked by: username_0 on 2021-02-24)

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>

**Tags:** ds.algorithms, time-complexity, matrix-product

---

## 2 answers

### Answer by username_1 on 2021-02-27. Score: 4 | Accepted answer

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

> **Comments:**
> **username_0**: It does! That is exactly what I was looking for!  

---

### Answer by username_0 on 2021-02-25. Score: 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](https://www.cs.tau.ac.il/%7Ezwick/papers/sparse.pdf)

> **Comments:**
> **username_2**: Can you clarify in the answer what exactly says the statement that you found in that paper?  
> **username_0**: 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 :-)  
> **username_3**: @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.  

---

