Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication
Popis výsledku anglicky
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.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2018
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
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
Počet stran výsledku
14
Strana od-do
1-14
Název nakladatele
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Místo vydání
Schloss Dagstuhl, Germany
Místo konání akce
Caen, France
Datum konání akce
28. 2. 2018
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—