License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2018.23
URN: urn:nbn:de:0030-drops-85050
URL: https://drops.dagstuhl.de/opus/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
Seminar: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Issue Date: 2018
Date of publication: 20.02.2018


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