Boolean Matrix Multiplication (Combinatorial) (Matrix Product)

From Algorithm Wiki
Jump to navigation Jump to search


Matrix multiplication of two boolean matrices (i.e. where all entries are in $F_2$ and addition is mod 2). Here, only "combinatorial" algorithms are considered.

Related Problems

Generalizations: Boolean Matrix Multiplication

Related: Matrix Multiplication, Matrix Product Verification, Distance Product, $(\min, \leq)$ Product


$n$: dimension of square matrix

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
2018 $O(n^{3} / log^{2.25} n)$ Exact Deterministic Time
Method of Four Russians 1970 $O(n^{3}/(log n)$^{2}) Exact Deterministic Time
Bansal, Williams 2009 $O(n^{3} * (log log n)$^{2} / log^{2.25} n) Exact Randomized Time
Bansal, Williams 2009 $O(n^{3} * (log log n)$^{2} / (w * (log n)^{7}/{6})) Exact Randomized Time
Chan 2015 $O(n^{3} * (log log n)$^{3} / log^{3} n) Exact Deterministic Time
Chan 2015 $O(n^{3} * (log w)$^{3} / (w * log^{2} n)) Exact Deterministic Time
Yu 2015 $O(n^{3}*poly(log log n)$/log^{4} n) Exact Deterministic Time