3
$\begingroup$

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.
$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Raphael May 19 '12 at 14:56
  • 5
    $\begingroup$ 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? $\endgroup$ – Gilles May 19 '12 at 21:17
  • $\begingroup$ 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? $\endgroup$ – Kaveh May 20 '12 at 0:26
  • $\begingroup$ @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. $\endgroup$ – Steven Stadnicki May 20 '12 at 1:50
  • $\begingroup$ @Steven, you are right, I take back my comment. $\endgroup$ – Kaveh May 20 '12 at 2:10
6
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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