Deterministic Communication Complexity of Equality if inputs differ by at most 1

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?

• In the third paragraph, is $k = n$? Nov 6, 2014 at 6:05

Hint: Compare the parities of the inputs. (Can you generalize this idea to at most $k$ differences?)
• Maybe I'm missing something, but if $k\le 2$ (instead of $1$), the parity check won't help if they differ exactly at $2$ indices, and it seems to me that you essentially get a fooling set of size 2^n / 2, which yields $\Omega(n)$, right? Nov 7, 2014 at 5:52
• Right, for larger $k$ you'll need something more than parity, but you can probably still do it with a constant number of bits. Nov 7, 2014 at 14:52