Sparse matrix multiplication and triangle listing in the congested clique model (Q2290622)

The paper deals with the problem of multiplying sparse matrices. For the parallel setting the distributed Congested Clique model, which consists of nodes in a fully connected synchronous network, is used. A new deterministic algorithm with a round complexity which depends on the sparsity of the input matrices is proposed. A special characteristic of the algorithm is that it speeds up matrix multiplication even if only one of the input matrices is sparse. The approach is extended to obtain a deterministic algorithm for sparsity-aware triangle listing in the Congested Clique model, in which each triangle needs to be known to some node.