patternMinor
Deterministic and randomized communication complexity of set equality
Viewed 0 times
equalitysetcommunicationrandomizeddeterministicandcomplexity
Problem
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.
(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.
Solution
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?
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?
Context
StackExchange Computer Science Q#1922, answer score: 6
Revisions (0)
No revisions yet.