DOI

The model of bulk-synchronous parallel (BSP) computation is an emerging paradigm of general-purpose parallel computing. We study the BSP complexity of subcubic algorithms for Boolean matrix multiplication. The communication cost of a standard Strassen-type algorithm is known to be optimal for general matrices. A natural question is whether it remains optimal when the problem is restricted to Boolean matrices. We give a negative answer to this question, by showing how to achieve a lower asymptotic communication cost for Boolean matrix multiplication. The proof uses a deep result from extremal graph theory, known as Szemerédi's Regularity Lemma. Despite its theoretical interest, the algorithm is not practical, because it works only on astronomically large matrices and involves huge constant factors.
Original languageEnglish
Title of host publicationAutomata, Languages and Programming (ICALP 1998)
Pages494-506
Number of pages13
DOIs
StatePublished - 1 Jan 1998

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Nature
Volume1443
ISSN (Print)0302-9743

ID: 127758693