Deterministic and randomized communication complexity of set equality

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.
• Note that this is the canonical example for communication complexity and there is plenty of material around; the linked Wikipedia article even addresses it. If there are questions that go beyond the article, please edit your question accordingly. – Raphael May 19 '12 at 14:56
• Ok, so this is your homework assignment. What is your question? What have you tried, how far did you get, and where are you stuck? – Gilles 'SO- stop being evil' May 19 '12 at 21:17
• Classical reference is: Kushilevitz, E. and N. Nisan, "Communication complexity", 1997. There is also a chapter in Arora and Barak's book. If this is an assignment in a course it would help if you mention which course it is, is it a complexity theory course? Is it a course about distributed algorithms? – Kaveh May 20 '12 at 0:26
• @Kaveh But the two bullet points read exactly like a homework problem and unlike any phrasing I would expect if this had come up in a practical application. – Steven Stadnicki May 20 '12 at 1:50
• @Steven, you are right, I take back my comment. – Kaveh May 20 '12 at 2:10

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?