Fall 2018

Boolean Matrix Multiplication Lower Bounds

Thursday, Sep. 13, 2018 4:30 pm5:00 pm

Add to Calendar


Michal Koucky (Charles University)

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.

Joint work with Debarati Das and Mike Saks.