2
$\begingroup$

In the universal relation $UR_n$ problem [1] of communication complexity, there are two players Alice and Bob. Alice gets a string $x \in \{0,1\}^n$, Bob gets a string $y \in \{0,1\}^n$ with the promise that $x \ne y$. The players exchange messages and the last player to receive a message must output an index $i \in [n]$ such that $x_i \ne y_i$. Moreover, the players have access to public randomness.

In a recent talk that I attended, the speaker mentioned that the following without giving a proof:

Any protocol for $UR_n$ can be transformed into an $UR_n$ protocol that has the additional property that each possible index $i$ where $x_i \ne y_i$ is output with the same probability, without changing the communication complexity.

I have been thinking about this for a while, but I could not come up with a proof. I would be thankful for any suggestions or pointers to literature.

[1] Mauricio Karchmer and Avi Wigderson. Monotone circuits for connectivity require super-logarithmic depth. In Proceedings of the twentieth annual ACM symposium on Theory of computing, STOC ’88, pages 539–550, New York, NY, USA, 1988. ACM.

$\endgroup$

1 Answer 1

0
$\begingroup$

If public randomness is allowed, then the two parties apply a common random permutation on their inputs, and XOR their inputs with a common random string.

Suppose that the inputs are $x,y$, and that they differ on the index set $I = \{i_1,\ldots,i_k\}$. For each permutation $\pi$ of $1,\ldots,k$, we can find a permutation $\alpha$ of $1,\ldots,n$ and a vector $z$ such that $(\alpha(x) \oplus z, \alpha(y) \oplus z) = (0^n,1^k0^{n-k})$, and furthermore, the $k$ initial coordinates originate from $i_{\pi(1)},\ldots,i_{\pi(k)}$. Choose such $\pi$ at random.

If we apply a random permutation and then a random XOR on $(\alpha(x) \oplus z, \alpha(y) \oplus z)$, then the resulting distribution is identical to what we would get if we applied a random permutation and then a random XOR on $x,y$ (this is because the object consisting of applying a permutation followed by an XOR forms a group).

If we translate the answer to the final pair to the pair $(\alpha(x) \oplus z, \alpha(y) \oplus z)$, then we get some distribution on the first $k$ coordinates. Translating this back to $(x,y)$, we get a uniformly random coordinate in $I$, since the permutation $\pi$ was random.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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