In the sparse matrix multiplication problem, the goal is to compute the product of two $n \times n$ matrices, given that these matrices are sparse, meaning the number of nonzero elements in the input matrices $m_{in}$ and/or the number of nonzero elements in the output matrix $m_{out}$ is much smaller than $n^2$. This paper explores a generalized problem of (approximately) computing the $k$ largest output entries, with approximation error solely dependent on the smaller entries. From the perspective of sparse recovery, this can be viewed as a robust variant of sparse matrix multiplication.
Despite extensive research on sparse matrix multiplication, almost no existing algorithms are robust in this sense. The one exception is Pagh's algorithm with a runtime of $\widetilde{O}(m_{in} + nk)$ [ITCS'12], and it remains open whether other algorithms can similarly be made robust.
Our principal contribution is a black-box reduction from robust sparse matrix multiplication to conventional sparse matrix multiplication with only polylogarithmic overhead. Specifically, we show that any sparse matrix multiplication algorithm with a runtime $T(n, m_{in}, m_{out})$ can be transformed into a robust algorithm running in time $\widetilde{O}(T(n, m_{in}, k))$. This reduction leverages an extensive toolkit from sparse recovery and intriguingly involves solving a knapsack-type problem.
By integrating the state-of-the-art algorithm for sparse matrix multiplication by Abboud, Bringmann, Fischer, and Künnemann [SODA'24], we achieve significantly improved bounds such as $O((m_{in} + k)^{1.346})$. Notably, in the regime where $k \geq m_{in}^{1.762}$, our reduction culminates in an almost-optimal $k^{1+o(1)}$-time algorithm.
Blogger's Review: This paper presents a novel approach by combining sparse matrix multiplication with robustness, offering new insights into the field. It enhances computational efficiency by leveraging existing algorithms, which is particularly significant when dealing with large-scale sparse data. This work is definitely worth attention.