License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2018.23
URN: urn:nbn:de:0030-drops-85050
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8505/
Go to the corresponding LIPIcs Volume Portal

Das, Debarati ; Koucký, Michal ; Saks, Michael

Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication

pdf-format:
LIPIcs-STACS-2018-23.pdf (0.5 MB)

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 Omega(n^3 / 2^{O( sqrt{ log n })}). Subsequently, we propose a more general model capable of simulating the
"Four Russian 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.

BibTeX - Entry

@InProceedings{das_et_al:LIPIcs:2018:8505,
  author =	{Debarati Das and Michal Kouck{\'y} and Michael Saks},
  title =	{{Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Rolf Niedermeier and Brigitte Vall{\'e}e},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8505},
  URN =		{urn:nbn:de:0030-drops-85050},
  doi =		{10.4230/LIPIcs.STACS.2018.23},
  annote =	{Keywords: Lower bounds, Combinatorial algorithm, Boolean matrix multiplication}
}

Keywords: Lower bounds, Combinatorial algorithm, Boolean matrix multiplication
Collection: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Issue Date: 2018
Date of publication: 27.02.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI