We have two computers, Comp1 and Comp2, which hold binary matrices A and B of size $n\times n$.We want to check if the matrices of the computers are identical except for exactly 1 entry.Comp1 has to send $O(n\log^2n)$ bits to Comp2 and Comp2 should return 0 or 1 (for no and yes respectively) for the answer.If the matrices differ by exactly 1 entry, Comp2 will answer 1 (yes) always.If they don't differ by exactly 1 entry, Comp2 will answer 0 in probability of at least $1/2$.Both computers can make any manipulation of their matrix before sending a message. Comp1 of course doesn't have to send a part of its matrix. It can send an answer of computation on its matrix, and Comp2 can make also any calculation it wants before answering.I've tried to solve it but whatever I tried it failed.
Randomized Algorithm with matrices
algorithms;randomized algorithms;randomness