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.
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.
Whether or not BMM can be solved faster than matrix multiplication over a ring or field is a major open problem.