The Time Complexity of Fully Sparse Matrix Multiplication
Amir Abboud, Karl Bringmann, Nick Fischer, Marvin Künnemann · Society for Industrial and Applied Mathematics eBooks · 2024
What is the time complexity of matrix multiplication of sparse integer matrices with min nonzeros in the input and mout nonzeros in the output? This paper provides improved upper bounds for this question for almost any choice of min vs. mout, and provides evidence that these new bounds might be optimal up to further progress on fast matrix multiplication.