  We consider the problem of multiplying sparse matrices (over a semiring)
where the number of non-zero entries is larger than main memory. In the
classical paper of Hong and Kung (STOC '81) it was shown that to compute a
product of dense $U \times U$ matrices, $\Theta \left(U^3 / (B \sqrt{M})
\right)$ I/Os are necessary and sufficient in the I/O model with internal
memory size $M$ and memory block size $B$.
  In this paper we generalize the upper and lower bounds of Hong and Kung to
the sparse case. Our bounds depend of the number $N =
\mathtt{nnz}(A)+\mathtt{nnz}(C)$ of nonzero entries in $A$ and $C$, as well as
the number $Z = \mathtt{nnz}(AC)$ of nonzero entries in $AC$.
  We show that $AC$ can be computed using $\tilde{O} \left(\tfrac{N}{B}
\min\left(\sqrt{\tfrac{Z}{M}},\tfrac{N}{M}\right) \right)$ I/Os, with high
probability. This is tight (up to polylogarithmic factors) when only semiring
operations are allowed, even for dense rectangular matrices: We show a lower
bound of $\Omega \left(\tfrac{N}{B}
\min\left(\sqrt{\tfrac{Z}{M}},\tfrac{N}{M}\right) \right)$ I/Os.
  While our lower bound uses fairly standard techniques, the upper bound makes
use of ``compressed matrix multiplication'' sketches, which is new in the
context of I/O-efficient algorithms, and a new matrix product size estimation
technique that avoids the ``no cancellation'' assumption.
