[Solved]: Deterministic and randomized communication complexity of set equality

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 $a\neq 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