Better Size Estimation for Sparse Matrix Products

We consider the problem of doing fast and reliable estimation of the number z of non-zero entries in a sparse boolean matrix product. This problem has applications in databases and computer algebra. Finally, we present experiments on real-world data sets that show the accuracy of both our methods to be significantly better than the worstcase analysis predicts.