1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ In the third paragraph, is $k = n$? $\endgroup$ – Yuval Filmus Nov 6 '14 at 6:05
1
$\begingroup$

Hint: Compare the parities of the inputs. (Can you generalize this idea to at most $k$ differences?)

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – somebody Nov 7 '14 at 5:52
  • $\begingroup$ Right, for larger $k$ you'll need something more than parity, but you can probably still do it with a constant number of bits. $\endgroup$ – Yuval Filmus Nov 7 '14 at 14:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.