The universal relation problem in communication complexity

Question

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.

Answer 1

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.