  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 relatively relaxed combinatorial model which is an
extension of the model by Angluin (1976), and we prove that the time required
by any algorithm for the BMM is at least $\Omega(n^3 / 2^{O( \sqrt{ \log n
})})$. Subsequently, we propose a more general model capable of simulating the
"Four Russians Algorithm". We prove a lower bound of $\Omega(n^{7/3} /
2^{O(\sqrt{ \log n })})$ for the BMM under this model. We use a special class
of graphs, called $(r,t)$-graphs, originally discovered by Rusza and Szemeredi
(1978), along with randomization, to construct matrices that are hard instances
for our combinatorial models.

Computational Complexity