Boolean Matrix Multiplication (Combinatorial) (Matrix Product)

Description

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

Parameters

$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

References/Citation

https://www.sciencedirect.com/science/article/pii/S0890540118300099