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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
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.
answered May 17, 2021 at 16:46
-
$\begingroup$ 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?). $\endgroup$ May 17, 2021 at 17:05
-
1$\begingroup$ 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. $\endgroup$ May 17, 2021 at 17:15
-
2$\begingroup$ 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) $\endgroup$ May 17, 2021 at 17:18
-
1$\begingroup$ You're welcome. Your titles made me LOL! (Funny that I would be chosen as "protector of the SETH"...) $\endgroup$ May 18, 2021 at 18:57
-
2$\begingroup$ Complexity nerdom starwars.fandom.com/wiki/Dark_Lord_of_the_Sith $\endgroup$– TurboMay 27, 2021 at 6:31