The Time Complexity of Fully Sparse Matrix Multiplication

What is the time complexity of matrix multiplication of sparse integer matrices with $m_{in}$ nonzeros in the input and $m_{out}$ nonzeros in the output? This paper provides improved upper bounds for this question for almost any choice of $m_{in}$ vs. $m_{out}$, and provides evidence that these new bounds might be optimal up to further progress on fast matrix multiplication.
Our main contribution is a new algorithm that reduces sparse matrix multiplication to dense (but smaller) rectangular matrix multiplication. Our running time thus depends on the optimal exponent $ω(a,b,c)$ of multiplying dense $n^a×n^b$ by $n^b×n^c$ matrices. We discover that when $m_{out}=Θ(m^r_{in})$ the time complexity of sparse matrix multiplication is $O(m^{σ+ϵ}_{in})$, for all $ϵ>0$, where $σ$ is the solution to the equation $ω(σ−1,2−σ,1+r−σ)=σ$. No matter what $ω(⋅,⋅,⋅)$ turns out to be, and for all $r∈(0,2)$, the new bound beats the state of the art, and we provide evidence that it is optimal based on the complexity of the all-edge triangle problem.
In particular, in terms of the input plus output size $m=m_{in}+m_{out}$ our algorithm runs in time $O(m^{1.3459})$. ... mehrEven for Boolean matrices, this improves over the previous $m^{\frac{2ω}{ω+1}+ϵ}=O(m^{1.4071})$ bound [Amossen, Pagh; 2009], which was a natural barrier since it coincides with the longstanding bound of all-edge triangle in sparse graphs [Alon, Yuster, Zwick; 1994]. We find it interesting that matrix multiplication can be solved faster than triangle detection in this natural setting. In fact, we establish an equivalence to a special case of the all-edge triangle problem.