# Boolean Matrix Multiplication (Matrix Product)

## 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

## 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
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)$
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}$
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}$
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}$
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
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
(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}$
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
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}$
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$
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