5
$\begingroup$

Consider two square matrices $A(x,y)$ and $B(y,z)$ of dimensions $N×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). Consider the decision problem of whether all non-zero entries of C are $\geq 2$. Is this problem known to be as hard as combinatorial BMM or triangle detection/k-clique detection using combinatorial algorithms? I am mainly interested in using "combinatorial" algorithms but any hardness result related to FMM would also instructive.

$\endgroup$
3
  • $\begingroup$ Why 2? As in, is it already known/easy for “at least 1”? $\endgroup$
    – daniello
    Jun 24 at 5:02
  • 1
    $\begingroup$ All non-zero entries of C will always be at least 1 since $A$ and $B$ contain 0/1 entries. So the answer to that question is always yes. $\endgroup$
    – karmanaut
    Jun 24 at 19:36
  • $\begingroup$ Is there a way on this website to send Bat-signal to lord commander @RyanWilliams? $\endgroup$
    – karmanaut
    2 days ago

1 Answer 1

0
$\begingroup$

This is not a proper answer but it might help you. I think a reduction to BMM might exist, but if it does, it will be hard to find: on the problem you ask for one bit (whether all ones are double-witnessed) while in BMM you ask for $n^2$ bits.

Now let us generalize this "witnessed 2 times" to witnessed $c$ times for any fixed $c\geq 1$.

  • If you were to ask for the positions in $C$ where the product is witnessed $c$ times then there would be an easy BMM reduction (see below).
  • In converse, if you were to ask whether there is at least one element that has $c$ witnesses then there would be an easy $O(n^2)$ algorithm (just compute the product and stop as soon as one element is witnessed $c$ times).
  • Your problem asks for all non zero element in $C$ to be witnessed $c$ times (at least), with $c=2$ and I don't know whether we can't do it but note that the case $c=1$ it is also unknown, as far as I know, how do it faster than BMM in deterministic time (see Freivalds' algorithm for a randomized efficient algorithm). Solving the case $c=2$ would also solve the case $c=1$ (see below). I don't know if we can adapt Freivalds' randomized algorithm for $c=2$.

Reduction : computing $\begin{bmatrix} A & A \\ 0 & 0 \end{bmatrix}\times \begin{bmatrix} B & 0 \\ B & 0 \end{bmatrix} = \begin{bmatrix} 2AB & 0 \\ 0 & 0 \end{bmatrix}$, hence finding the doubly witnessed elements in $ \begin{bmatrix} 2AB & 0 \\ 0 & 0 \end{bmatrix}$ gives $AB$ and testing whether the doubly witnessed elements correspond to all non-zero position of $ \begin{bmatrix} C & 0 \\ 0 & 0 \end{bmatrix}$ gives the the multiplication check of $AB=C$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.