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, 2022 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, 2022 at 19:36
  • $\begingroup$ Is there a way on this website to send Bat-signal to lord commander @RyanWilliams? $\endgroup$
    – karmanaut
    Jun 29, 2022 at 4:16

1 Answer 1

1
$\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$
3
  • $\begingroup$ Thanks! This is definitely food for thought. One thing I'd like to point out - your reasoning for why BMM reduction might be hard to find might not be true. See the abstract and section 1.1 kam.mff.cuni.cz/~matousek/cla/tria-mmult.pdf. The same intuition also holds for triangle detection and BMM since detection is 1 bit but BMM is $n^2$ but reductions are there! I strongly feel there should be something from triangle detection here -- perhaps my question is equivalent to asking whether every edge in a graph participates in at least 2 triangles but I am not able to show it (yet). $\endgroup$
    – karmanaut
    Jul 1, 2022 at 17:42
  • $\begingroup$ Agreed, but I am not claiming that such a reduction does not exist just that if it does, it will likely be a non "trivial" one. I have also seen people use product vector-matrix-vector to optimize matrix-vector product so you can look there. Also note that my last point reduces to the problem "how to deterministically test whether AB=C?" which as far as I know, is open. $\endgroup$
    – Louis
    Jul 1, 2022 at 17:58
  • $\begingroup$ Another question I had, $C$ is the output of $AB$ but in the reduction, it seems $C$ is used as an input just like $A,B$. Is my understanding correct? We don't want to compute $C$ explicitly (otherwise it is BMM amount of work already. Second, $c=1$ should be trivial, right? Each non-zero entry of $AB$ is guaranteed to be at least $1$. $\endgroup$
    – karmanaut
    Jul 3, 2022 at 4:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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