The set equality problem in 2 party communication complexity is known to require $n$ bits of communication between Alice and Bob, for $n$-bit inputs $X$ and $Y$.
Suppose that we promise that the symmetric difference of $X$ and $Y$ is $\le 1$. Is the required communication for a deterministic protocol still $\Omega(n)$?
My thoughts: I believe that the complexity becomes $O(\log n)$ because of the following: When Alice gets its input $X$ of size $k$, she knows that Bob's input differs at $\le 1$ index. Thus, there are only $\le {n \choose 1}n + 1 = O(n^2)$ possibilities for $Y$, given $X$; the "+1" is the case where $X=Y$. So there should be a way to convey this information from Bob to Alice using only $O(\log n)$ bits. Is my reasoning correct?
