在稀疏矩阵乘法问题中，我们的目标是计算两个 $n \times n$ 矩阵的乘积，前提是这些矩阵是稀疏的，即输入矩阵中的非零元素数量 $m_{in}$ 和/或输出矩阵中的非零元素数量 $m_{out}$ 远小于 $n^2$。本文探讨了一个广义问题，即（近似地）计算 $k$ 个最大的输出项，其近似误差仅依赖于较小的项。从稀疏恢复的角度看，这可以视为稀疏矩阵乘法的鲁棒变体。
尽管已有大量研究致力于稀疏矩阵乘法，但几乎没有现有算法在此意义上是鲁棒的。唯一的例外是 Pagh 的算法，其运行时间为 $\widetilde{O}(m_{in} + nk)$ [ITCS'12]，而其他算法是否也可以类似地变得鲁棒仍然是一个未解之谜。
我们的主要贡献是一个黑箱约简，将鲁棒稀疏矩阵乘法转化为常规稀疏矩阵乘法，仅需多对数级的开销。具体来说，我们展示了任何运行时间为 $T(n, m_{in}, m_{out})$ 的稀疏矩阵乘法算法可以被转化为一个鲁棒算法，其运行时间为 $\widetilde{O}(T(n, m_{in}, k))$。这一约简利用了稀疏恢复的广泛工具包，并且有趣的是，还涉及解决一种背包类型的问题。
通过引入 Abboud、Bringmann、Fischer 和 Künnemann 的稀疏矩阵乘法的前沿算法 [SODA'24]，我们实现了显著改进的界限，例如 $O((m_{in} + k)^{1.346})$。值得注意的是，在 $k \geq m_{in}^{1.762}$ 的范围内，我们的约简最终形成了一个几乎最优的 $k^{1+o(1)}$ 时间算法。
博主点评： 本文通过黑箱约简将稀疏矩阵乘法与鲁棒性相结合，为这一领域提供了新的思路，尤其是在处理大规模稀疏数据时，具有重要的实际意义。利用现有算法的优势，进一步提升了计算效率，值得关注。