In the paper Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems, the authors consider the universal relation problem in 2-party communication complexity, which is defined as follows:
Consider the following two player communication game. Alice gets a string $x \in \{0,1\}^n$, Bob gets $y \in \{0, 1\}^n$ with the promise that $x \ne y$. Alice and Bob exchange messages and the last player must output an index $i \in [n]$ such that $x_i \ne y_i$.
As part of their proof, the authors use the following lemma, for which they only give a very short proof in the appendix. I have pasted both (literally) below:
Lemma 7. Any protocol for UR can be turned into one that outputs every index $i \in [n]$ with $x_i \ne y_i$ with the same probability. The new protocol uses a joint random source. The number of bits sent, the number of rounds and the error probability does not change.
Proof of Lemma 7. Using the joint random source, the players take a uniform random permutation $\pi$ of $[n]$ and use it to permute the digits of $x$ and $y$. Further they take a uniform random subset $S \subseteq [n]$ and flip the digits with coordinates in $S$. This requires no communication. Then they run the original protocol on the modified inputs and report $\pi^{−1}(i)$ if the original protocol reports $i$. All indices where $x$ and $y$ differ are reported with equal probability by symmetry. QED.
I'm having troubles verifying this proof. My understanding is this:
- Alice and Bob use joint randomness to sample a permutation $\pi$. OK.
- They both apply $\pi$ to their respective input. OK.
- Then, it says "Further they take a uniform random subset $S \subseteq [n]$ and flip the digits with coordinates in $S$." I'm not sure what this means and why this set is needed since they don't seem to be using $S$ in the rest of the proof!
- Alice and Bob run the original protocol on the modified inputs and report $\pi^{−1}(i)$ if the original protocol reports $i$. They claim that this procedure yields all elements where $x \ne y$ with equal probability "by symmetry".
Could someone explain to me the purpose of Step 3 and provide some hints why this gives each coordinate where $x \ne y$ with same probability?
