Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10387319" target="_blank" >RIV/00216208:11320/18:10387319 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.4230/LIPIcs.STACS.2018.23" target="_blank" >https://doi.org/10.4230/LIPIcs.STACS.2018.23</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2018.23" target="_blank" >10.4230/LIPIcs.STACS.2018.23</a>

Result language
angličtina
Original language name
Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication
Original language description
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.
Czech name
—
Czech description
—

Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
35th Symposium on Theoretical Aspects of Computer Science, {STACS} 2018, February 28 to March 3, 2018, Caen, France
ISBN
978-3-95977-062-0
ISSN
—
e-ISSN
neuvedeno
Number of pages
14
Pages from-to
1-14
Publisher name
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Place of publication
Schloss Dagstuhl, Germany
Event location
Caen, France
Event date
Feb 28, 2018
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)