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.
Язык оригиналаанглийский
Название основной публикацииAutomata, Languages and Programming (ICALP 1998)
Страницы494-506
Число страниц13
DOI
СостояниеОпубликовано - 1 янв 1998

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ИздательSpringer Nature
Том1443
ISSN (печатное издание)0302-9743

ID: 127758693