3
$\begingroup$

I'm new to communication theory and I've been wondering where the following simple argument fails:

Equality Problem We have two players, player 1 Alice who gets an $n$-bit vector $X$ and player 2 Bob who gets an $n$-bit vector $Y$. We want one of them to output $1$ if and only if for all indices $i:$ $X[i] = Y[i]$.
Suppose that I choose the inputs $X$ and $Y$ uniformly at random from the set $\{0,1\}^n$. Initially, Alice knows nothing about Bob's input $Y$. Consider a protocol $P$ for equality. Alice and Bob run $P$ and assume that $P$ outputs $1$. By the correctness of $P$, Alice knows that for each index $i$, $Y[i] = X[i]$. Thus Alice has learned $|Y|=n$ bits . Doesn't this immediately imply the $\Omega(n)$ lower bound for $P$?

Note: Of course, I know that the above argument must be flawed since we can solve equality with $O(\log n)$ bits when allowing randomization. I'm just trying to understand why my proof attempt is flawed.

$\endgroup$
1
$\begingroup$

This vague argument can be made to work for deterministic communication complexity. In the randomized setting, protocols are allowed to err. Consider the standard protocol in which both players exchange a random hash of their inputs to some set of size $2^m$. They only learn $m$ bits of each other's input. When both hashes agree, they aren't completely sure that $X=Y$, and in particular no party has learned the other party's input.

$\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.