<p>There is no known algorithm, and no known barrier to this. I'm also of the belief that, ultimately, BMM should have a faster algorithm than standard MM.</p>
<p>I don't know if I have a lot of strong reasons why I believe this, other than intuition. Maybe one data point is the fact that in the cell-probe model, one can do Boolean matrix vector multiplication much faster than n^2 probes, but this is not known for matrix vector multiplication over a small field. For a reference, see e.g. Larsen and Williams SODA 2017.</p>

CC BY-SA 4.0
2024-10-20T19:26:02.543Z
2024-10-20T19:26:02.543Z
Ryan Williams
<p>Obviously, we can reduce Boolean Matrix Multiplication to classic MM (if the result is at least <span class="math-container">$1$</span>, we consider it as &quot;true&quot; or <span class="math-container">$1$</span>), which yields an algorithm for BMM in <span class="math-container">$n^{\omega}$</span>. My question is: Is there an algorithm that can solve BMM even faster? Or, more likely, is there a hardness result showing this is unlikely/impossible?</p>

CC BY-SA 4.0
2024-10-20T17:04:00.253Z
Well, what about the following BMM to MM reduction: consider the boolean matrix as $1$ and $0$. Multiply by any classical MM algorithm. If $c_{i,j}\geq 1$, set it to $1$ (equivalently: $true$).
Mařík Savenko
CC BY-SA 4.0
2024-10-20T17:45:35.640Z
My bad, I was talking about combinatorial BMM. If you use a classical (algebraic) algorithm, it should of course work.
Lamine
<matrix-product><boolean-matrix><fine-grained>
Possibility of BMM in less than $n^{\omega}$?
Mařík Savenko
# Possibility of BMM in less than $n^{\omega}$?

(Asked by: username_0 on 2024-10-20)

Obviously, we can reduce Boolean Matrix Multiplication to classic MM (if the result is at least $1$, we consider it as "true" or $1$), which yields an algorithm for BMM in $n^{\omega}$. My question is: Is there an algorithm that can solve BMM even faster? Or, more likely, is there a hardness result showing this is unlikely/impossible?

**Tags:** matrix-product, boolean-matrix, fine-grained
> **Comments:**
> **username_0**: Well, what about the following BMM to MM reduction: consider the boolean matrix as $1$ and $0$. Multiply by any classical MM algorithm. If $c_{i,j}\geq 1$, set it to $1$ (equivalently: $true$).  
> **username_1**: My bad, I was talking about combinatorial BMM. If you use a classical (algebraic) algorithm, it should of course work.  

---

## 1 answers

### Answer by username_2 on 2024-10-20. Score: 6 | Accepted answer

There is no known algorithm, and no known barrier to this. I'm also of the belief that, ultimately, BMM should have a faster algorithm than standard MM.

I don't know if I have a lot of strong reasons why I believe this, other than intuition. Maybe one data point is the fact that in the cell-probe model, one can do Boolean matrix vector multiplication much faster than n^2 probes, but this is not known for matrix vector multiplication over a small field. For a reference, see e.g. Larsen and Williams SODA 2017.


---

