<p>You can reduce Boolean matrix multiplication (BMM) to this problem. (BMM is matrix multiplication over the OR/AND semiring with 0 and 1.) Imagine adding one more column to the first matrix A and one more row to the first matrix B, both of which are all-ones. If the BMM of A and B had a 0 in an entry, your new product over the integers will have 1, and if the BMM had a 1 in an entry, your new product over the integers will have at least a 2. Thus determining these &quot;exactly one&quot; entries is at least as hard as BMM.</p>
<p>Whether or not BMM can be solved faster than matrix multiplication over a ring or field is a major open problem.</p>

CC BY-SA 4.0
2021-05-17T17:05:00.063Z
Very cool! The problem is BMM-hard is more than enough for my purpose. For your last statement, you mean BMM can be solved faster than some "combinatorial" matrix multiplication algorithm over a ring or field right? We can solve general matrix multiplication in $O(N^\omega)$ time which can be used for BMM but we don't know if we can do BMM in subcubic time, which is the best combinatorial matrix multiplication algorithm (modulo log factors) we know of (right?).
karmanaut
CC BY-SA 4.0
2021-05-17T17:15:25.020Z
Ah ok I get your comment now -- maybe BMM can be done even faster than $O(N^\omega)$ given that we have boolean entries (which intuitively should be "easier" to deal with). Thanks @ryan-williams -- King of fine-grained complexity, protector of the SETH.
karmanaut
CC BY-SA 4.0
2021-05-17T17:18:15.143Z
My last statement says nothing about "combinatorial" algorithms. There is another open problem about combinatorial BMM but is not really well-defined, compared to the problem I stated. Again, stated slightly differently: it is open whether BMM can be solved in o(n^omega) time where omega is the matrix multiplication exponent (for arbitrary rings, or for fields)
Ryan Williams
CC BY-SA 4.0
2021-05-18T18:57:15.850Z
You're welcome. Your titles made me LOL! (Funny that I would be chosen as "protector of the SETH"...)
Ryan Williams
CC BY-SA 4.0
2021-05-27T06:31:10.200Z
Complexity nerdom https://starwars.fandom.com/wiki/Dark_Lord_of_the_Sith
Turbo
CC BY-SA 4.0
2021-05-27T06:35:07.263Z
Actually @RyanWilliams seeks to destroy SETHdom afaik.
Turbo
CC BY-SA 4.0
2021-05-29T04:47:09.107Z
@1.. Fate loves irony :-)
karmanaut
CC BY-SA 4.0
2021-05-17T16:46:52.623Z
2021-05-17T16:46:52.623Z
Ryan Williams
<p>Consider two square matrices <span class="math-container">$A(x,y)$</span> and <span class="math-container">$B(y,z)$</span> of dimensions <span class="math-container">$N \times N$</span> containing boolean entries. Consider the output product matrix <span class="math-container">$C(x,z)$</span> where <span class="math-container">$C = AB$</span> (not boolean matrix multiplication but the entries store the count of how many <span class="math-container">$y$</span> generate a given output entry). My goal is to find only the output entries in <span class="math-container">$C$</span> which are generated by exactly one value of <span class="math-container">$y$</span> (i.e. a unique witness). In other words, I want to find all <span class="math-container">$(i,j)$</span> such that <span class="math-container">$C(i,j) = 1$</span>. Clearly, I can simply perform the matrix multiplication and iterate over <span class="math-container">$C$</span> to identify the output with unique witnesses but can we do better? Is this problem as hard as matrix multiplication itself? Are there are any known reductions that consider the problem of finding output that is generated by a unique <span class="math-container">$y$</span> value? I am interested in deterministic algorithms but even something probabilistic may be insightful.</p>

<ds.algorithms><graph-algorithms><matrices>
Finding output with unique witness in matrix multiplication
karmanaut
# Finding output with unique witness in matrix multiplication

(Asked by: username_0 on 2021-05-17)

Consider two square matrices $A(x,y)$ and $B(y,z)$ of dimensions $N \times N$ containing boolean entries. Consider the output product matrix $C(x,z)$ where $C = AB$ (not boolean matrix multiplication but the entries store the count of how many $y$ generate a given output entry). My goal is to find only the output entries in $C$ which are generated by exactly one value of $y$ (i.e. a unique witness). In other words, I want to find all $(i,j)$ such that $C(i,j) = 1$. Clearly, I can simply perform the matrix multiplication and iterate over $C$ to identify the output with unique witnesses but can we do better? Is this problem as hard as matrix multiplication itself? Are there are any known reductions that consider the problem of finding output that is generated by a unique $y$ value? I am interested in deterministic algorithms but even something probabilistic may be insightful.

**Tags:** ds.algorithms, graph-algorithms, matrices

---

## 1 answers

### Answer by username_1 on 2021-05-17. Score: 3 | Accepted answer

You can reduce Boolean matrix multiplication (BMM) to this problem. (BMM is matrix multiplication over the OR/AND semiring with 0 and 1.) Imagine adding one more column to the first matrix A and one more row to the first matrix B, both of which are all-ones. If the BMM of A and B had a 0 in an entry, your new product over the integers will have 1, and if the BMM had a 1 in an entry, your new product over the integers will have at least a 2. Thus determining these "exactly one" entries is at least as hard as BMM.

Whether or not BMM can be solved faster than matrix multiplication over a ring or field is a major open problem.

> **Comments:**
> **username_0**: Very cool! The problem is BMM-hard is more than enough for my purpose. For your last statement, you mean BMM can be solved faster than some "combinatorial" matrix multiplication algorithm over a ring or field right? We can solve general matrix multiplication in $O(N^\omega)$ time which can be used for BMM but we don't know if we can do BMM in subcubic time, which is the best combinatorial matrix multiplication algorithm (modulo log factors) we know of (right?).  
> **username_0**: Ah ok I get your comment now -- maybe BMM can be done even faster than $O(N^\omega)$ given that we have boolean entries (which intuitively should be "easier" to deal with). Thanks @ryan-williams -- King of fine-grained complexity, protector of the SETH.  
> **username_1**: My last statement says nothing about "combinatorial" algorithms. There is another open problem about combinatorial BMM but is not really well-defined, compared to the problem I stated. Again, stated slightly differently: it is open whether BMM can be solved in o(n^omega) time where omega is the matrix multiplication exponent (for arbitrary rings, or for fields)  
> **username_1**: You're welcome. Your titles made me LOL! (Funny that I would be chosen as "protector of the SETH"...)  
> **username_2**: Complexity nerdom https://starwars.fandom.com/wiki/Dark_Lord_of_the_Sith  
> **username_2**: Actually @RyanWilliams seeks to destroy SETHdom afaik.  
> **username_0**: @1.. Fate loves irony :-)  

---

