Consider a boolean matrix $A$ of size $N \times N$ and let $A^\top$ be its transpose. Let $C = AA^\top$ be the boolean matrix multiplication (BMM) result and let $c$ be the number of non-negative entries in $C$. My goal is to flip one bit in $A$ from $0$ to $1$ to create a new matrix $B$ such that $C' = B B^\top$ is the BMM result and if $c'$ is the number of non-negative entries in $C'$, we wish to maximize $c' - c$. In other words, by flipping one entry, we wish to $\it maximize$ the incremental output generated by BMM of the resulting matrix. Has this problem been studied in literature and if yes, is this problem as hard as BMM itself?

I am also interested in the decremental analogue of the problem where we can flip one bit in A from $1$ to $0$ to maximize the decrease in the output between BMM of the original matrix with its transpose and the new matrix with its transpose.



Your Answer

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