4
$\begingroup$

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.

$\endgroup$
0

Your Answer

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

Browse other questions tagged or ask your own question.