K. Bringmann

Robustifying Sparse Matrix Multiplication

This paper explores the generalized problem of (approximately) computing the largest output entries, with an approximation error dependent solely on the smaller entries, from the viewpoint of sparse recovery, and shows that any sparse matrix multiplication algorithm with running time T(n, m_{in}, m_{out}) can be transformed into a robust algorithm running in time O(T(n, m_{in), k)$.