let us consider Alice and Bob communicate over channel bit by bit. They have one string over $\{0,1\}^{*}$. Let $x$ (uniformly at random) be the string that Bob have and $y$ be the string that Alice have. They want to check whether there strings are same or not.

On simple algorithm is exchange $n$ bits one by one. We want to solve this problem with few bits exchanged between Alice and Bob.

My Idea : We will randomly select $k = O(\log {n})$ many bits and exchange only these bits. In this probability of error is going to be less than $1/2^{k}$ (because probability of making error for one bit is 1/2) and as each time we are randomly selecting the bits overall probability of error will be less than $\frac{1}{2^{k}}$.

Question : Is my solution optimal one to solve the problem described above?


1 Answer 1


By simply exchanging random indices you cannot hope to do better than $\Omega(n)$ communication if you want constant error probability. If the strings differ in only a single bit, and you exchange $k$ indices, then the probability of finding the index in which they differ is $\frac{k}{n}$, so if you want this to be constant you must have $k=\Omega(n)$.

The randomized communication complexity can indeed be reduced to $O(\log n)$, but you're going to need stronger arguments. One way to do this is to encode both words with an error correcting code having a large distance, and then use your algorithm (naive sampling) on the codewords.

To elaborate on the above idea, the choice of code doesn't really matter, as the only property you need in order to make naive sampling work is large distance. One example is using Reed-Solomon, given $s\in\{0,1\}^n$, think of it as a string of length $k$ over $\mathbb{F_q}$, with $q=n$ and $k=\frac{n}{\log n}$. In that case you can think of $s=s_0,...,s_{k-1}$ as the polynomial $P_s=s_0+s_1x+...+s_k x^{k-1}$ over $\mathbb{F}_q$. If $s_1\neq s_2$ then their corresponding polynomials agree on at most $k-1$ points in $\mathbb{F}_q$, which means they will differ on at least $n-(k-1)=n\left(1-\frac{1}{\log n}\right)+1$ points in $\mathbb{F}_{q=n}$. Thus, with high probability, $P_{s_1},P_{s_2}$ will disagree on a random point in $\mathbb{F}_q$. This protocol requires you to send three elements in $\mathbb{F}_q$ (a point and both polynomials evaluations on it), which results in $O(\log q)=O(\log n)$ communication.

This is only one option, there are many randomized protocols for equality. One example is using a simple public coins protocol, in which both parties share two random strings $r,r'\sim U_n$, and exchange the values of $\langle xr,r'\rangle, \langle yr,r'\rangle$. This succeeds with probability $\frac{1}{2}$, and you can turn it into a private coin protocol with logarithmic overhead in communication, see these notes for details. Another option is to choose a prime $p\le poly(n)$ at random, and exchange $x,y\bmod p$. If $x\neq y$ then with high probability $p$ will not divide $x-y$.

  • $\begingroup$ I edited the original answer to include concrete protocols (I'd rather not depend on the comments). $\endgroup$
    – Ariel
    Nov 27, 2017 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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