TY - GEN
T1 - Lower bounds for combinatorial algorithms for Boolean Matrix Multiplication
AU - Das, Debarati
AU - Koucký, Michal
AU - Saks, Michael
N1 - Funding Information:
Funding The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013)/ERC Grant Agreement no. 616787. The second author was also partially supported by the Center of Excellence CE-ITI under the grant P202/12/G061 of GA ČR. The third author was supported in part by the Simons Foundation under Award 332622.
Publisher Copyright:
© Debarati Das, Michal Koucký, and Mike Saks.
PY - 2018/2/2
Y1 - 2018/2/2
N2 - 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 (n3/2O(log n)). Subsequently, we propose a more general model capable of simulating the "Four Russian Algorithm". We prove a lower bound of (n7/3/2O(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.
AB - 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 (n3/2O(log n)). Subsequently, we propose a more general model capable of simulating the "Four Russian Algorithm". We prove a lower bound of (n7/3/2O(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.
UR - http://www.scopus.com/inward/record.url?scp=85044542085&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85044542085&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.STACS.2018.23
DO - 10.4230/LIPIcs.STACS.2018.23
M3 - Conference contribution
AN - SCOPUS:85044542085
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018
A2 - Vallee, Brigitte
A2 - Niedermeier, Rolf
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018
Y2 - 28 February 2018 through 3 March 2018
ER -