# The universal relation problem in communication complexity

In the universal relation $$UR_n$$ problem  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.

 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.

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.