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.
For the first point, try a counting argument. How many different messages $m(a)$ can $B$ receive, if $|m(a)|&lt;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?