Lower bounds for Combinatorial Algorithms for Boolean Matrix Multiplication

Debarati Das, Michal Koucký, Michael Saks

In this paper we propose models of combinatorial algorithms for the Boolean Matrix Multiplication (BMM), and prove lower bounds on computing BMM in these models. First, we give a r…