Randomized Algorithm with matrices 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.
Let's start by assuming that we have two bit vectors $A,B$ of size $m$ instead of two matrices – the matrix structure is unhelpful.

Let $w \in \{\pm1\}^m$ be chosen randomly, and let $\varphi = x \mapsto \langle x,w \rangle \pmod{3}$. If $A,B$ differ on the coordinates in $S$ then
$$ \varphi(A) - \varphi(B) = \sum_{i \in S} (A_i - B_i) w_i \pmod{3}. $$
The distribution of this is the same as the distribution of
$$ \Delta = \sum_{i \in S} w_i \pmod{3}. $$
Suppose $s = |S|$. In order to compute the distribution of $\Delta$, let $\omega$ be a primitive third root of unity, and consider
$$ \left(\frac{\omega + \omega^{-1}}{2}\right)^s = \frac{(-1)^s}{2^s} = \left(\frac{1}{3} + \frac{(-1)^s}{3 \cdot 2^{s-1}}\right) \omega^0 + \left(\frac{2}{3} - \frac{(-1)^s}{3 \cdot 2^{s-1}}\right) \frac{\omega + \omega^{-1}}{2}. $$
For concreteness, here is the probability that $\Delta = 0$ for $s = 0,1,2,\ldots$:
$$ 1,0,\frac{1}{2},\frac{1}{4},\ldots $$
These probabilities tend to $1/3$ exponentially fast, alternately being above and below it. In particular, if $s = 1$ then $\Pr[\Delta = 0] = 0$, and otherwise $\Pr[\Delta = 0] \geq 1/4$.

This suggests the following algorithm, in the case in which the two computers are allowed shared randomness:


Both computers extract $k$ random functionals $\varphi_1,\ldots,\varphi_k$ from the common randomness.
Computer 1 sends $\varphi_1(A),\ldots,\varphi_k(A)$ to Computer 2.
Computer 2 computes $\varphi_1(B),\ldots,\varphi_k(B)$, and outputs Yes if $\varphi_i(A) \neq \varphi_i(B)$ for all $1 \leq i \leq k$.


If the two vectors differ in exactly one location, then Computer 2 always outputs Yes. Otherwise, it outputs No with probability at least $1 - (3/4)^k$. Choosing $k = 3$, we get $1 - (3/4)^3 &gt; 1/2$.

What if the computers are not allowed shared randomness? A standard trick allows us to simulate shared randomness using an overhead of $O(\log m)$. In total, the communication complexity is $O(\log m)$.