# Finding output with unique witness in matrix multiplication

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.

• 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 May 17 at 17:05
• 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 May 17 at 17:15