Censor-Hillel, Leitersdorf, and Turner [1]} obtained an algorithm for sparse graphs, with a complexity of \({O}(m/n^{5/3} + 1)\)  which is similar to, but slightly improves upon, the complexity of the algorithm of [2]}, by polylogarithmic factors. The algorithm of [1]} is deterministic and is based on an algorithm for sparse matrix multiplication, which completes in
\(O((\rho _S\rho _Tn)^{1/3}+1)\)  rounds, where \(S\)  and \(T\)  are the input matrices and \(\rho _A\)  is the average number of non-zero elements per row of a matrix \(A\)  (i.e., it is the number of non-zero elements of \(A\) , divided by \(n\) ).The sparse matrix multiplication algorithm of [1]} can also be converted to the \(k\) -machine model, in which it has a complexity of \(O(n^{4/3}(\rho _S\rho _T)^{1/3}/k^{5/3}+1)\)  rounds. While the aforementioned semi-ring matrix multiplication algorithm of [5]} assigns the \(n^3\)  element-wise multiplication to the nodes in an optimal manner, it applies to the worst case. The general approach used by[1]} for sparse matrix multiplication is to assign the element-wise multiplications to nodes in a way which is optimal given the input sparsity. The way this is done is by load balancing the number of non-zero elements that each node needs to send and receive in order for all element-wise multiplications to be computed.
