Boolean Matrix Multiplication (Matrix Product)

From Algorithm Wiki
Jump to navigation Jump to search

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