Lower bounds for combinatorial algorithms for Boolean Matrix Multiplication

Debarati Das, Michal Koucký, Michael Saks

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication35th Symposium on Theoretical Aspects of Computer Science, STACS 2018
EditorsBrigitte Vallee, Rolf Niedermeier
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770620
DOIs
StatePublished - Feb 2 2018
Event35th Symposium on Theoretical Aspects of Computer Science, STACS 2018 - Caen, France
Duration: Feb 28 2018Mar 3 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume96
ISSN (Print)1868-8969

Other

Other35th Symposium on Theoretical Aspects of Computer Science, STACS 2018
CountryFrance
CityCaen
Period2/28/183/3/18

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Boolean Matrix Multiplication
  • Combinatorial Algorithm
  • Lower Bounds

Cite this