Boolean Matrix Multiplication

Description

Matrix multiplication of two boolean matrices (i.e. where all entries are in $F_2$ and addition is mod 2)

Related Problems

Generalizations: Matrix Multiplication

Subproblem: Boolean Matrix Multiplication (Combinatorial)

Related: 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
Output-Sensitive Quantum BMM	2018	O*( \min \{n^{1/3} L^{17/{3}0}, n^{1.5} L^{1/4}\})		Exact	Quantum	Time
	2018	$O(n^{3} / log^{2.25} n)$		Exact	Deterministic	Time
O'Neil	1973	$O(n^{3})$		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

Reductions TO Problem

Problem	Implication	Year	Citation	Reduction
CFG Parsing	if: to-time: $O(gn^{3-\epsilon})$ for some $\epsilon > {0}$ where $g$ is the size of the CFG and $n$ is the size of the string then: from-time: $O(n^{3-\epsilon/3})$ where $n \times n$ matrix	2002	https://arxiv.org/abs/cs/0112018	link
Independent Set Queries	if: to-time: $O(n^{2} / \log^c n)$ to answer all subsequent batches of $\log n$ independent set queries from a graph that takes $O(n^k)$ time to preprocess for some $c,k > {0}$ then: from-time: $O(n^{3} / \log^{c+1} n)$	2018	https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 6.5	link
2-sensitive incremental st-reach	assume: BMM then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$	2017	https://arxiv.org/pdf/1703.01638.pdf	link
1-sensitive incremental ss-reach	assume: BMM then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$	2017	https://arxiv.org/pdf/1703.01638.pdf	link
ap-reach	assume: BMM then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$	2017	https://arxiv.org/pdf/1703.01638.pdf	link
2-sensitive (7/5)-approximate st-shortest paths	assume: BMM then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ in undirected unweighted graphs	2017	https://arxiv.org/pdf/1703.01638.pdf	link
1-sensitive (3/2)-approximate ss-shortest paths	assume: BMM then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ in undirected unweighted graphs	2017	https://arxiv.org/pdf/1703.01638.pdf	link
(5/3)-approximate ap-shortest paths	assume: BMM then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$	2017	https://arxiv.org/pdf/1703.01638.pdf	link
1-sensitive (4/3)-approximate decremental diameter	assume: BMM then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ in undirected unweighted graphs	2017	https://arxiv.org/pdf/1703.01638.pdf	link
1-sensitive (4/3)-approximate decremental eccentricity	assume: BMM then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$	2017	https://arxiv.org/pdf/1703.01638.pdf	link
1-sensitive decremental st-shortest paths	assume: BMM then: for directed unweighted graphs with $n$ vertices and $m \geq n$ edges require either $m^{1-o({1})}\sqrt{n}$ preprocessing time or $m^{1-o({1})}/\sqrt{n}$ query time for every function $m$ of $n$	2017	https://arxiv.org/pdf/1703.01638.pdf	link

Reductions FROM Problem

Problem	Implication	Year	Citation	Reduction
CFG Parsing	if: to-time: $O(n^{3-\epsilon})$ for some $\epsilon > {0}$ where $n \times n$ matrix then: from-time: $O(gn^{3-\epsilon})$ where $g$ is the size of the CFG	1975	https://www.sciencedirect.com/science/article/pii/S0022000075800468	link

References/Citation

https://arxiv.org/pdf/2010.05846.pdf