Problem Detail: Two processors $A, B$ with inputs $a in {0, 1}^n$ (for $A$) and $b in {0, 1}^n$ (for $B$) want to decide whether $a = b$. $A$ does not know $B$’s input and vice versa. A can send a message $m(a) in {0, 1}^n$ which $B$ can use to decide $a = b$. The communication and computation rules are called a protocol.
- Show that every deterministic protocol must satisfy $|m(a)| ge n$.
- State a randomized protocol that uses only $O(log_2n)$ Bits. The protocol should always accept if $a = b$ and accept with probability at most $1/n$ otherwise. Prove its correctness.
Asked By : user1374864
Answered By : Syzygy
For the first point, try a counting argument. How many different messages $m(a)$ can $B$ receive, if $|m(a)|<n$? How many different strings can $A$ have? For the second point, try first analyzing the trivial randomized protocol (randomly fixing $log(n)$ positions of the string and sending these bits of $a$). Clearly, this protocol always accepts if $a=b$. Assume $aneq b$, what is the probability that $log(n)$ randomly picked bits are the same? Does that suffice?
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1922
