2026-07-20T11:15:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8505 2024-03-06T10:42:18Z ddc:004 open_access

Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication Das, Debarati Koucký, Michal Saks, Michael Lower bounds Combinatorial algorithm Boolean matrix multiplication 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Debarati Das and Michal Koucký and Michael Saks 2018 Is Part Of LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2018.23 urn:nbn:de:0030-drops-85050 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.23 eng https://creativecommons.org/licenses/by/3.0/legalcode