We answer four questions from a recent paper of Rao and Shinkar on Lipschitz bijections between functions from $\{ 0,1\}^n$ to $\{ 0,1\}$. (1) We show that there is no $O(1)$-bi-Lipschitz bijection from $\mathrm{ Dictator}$ to $\mathrm{ XOR}$ such that each output bit depends on $O(1)$ input bits. (2) We give a construction for a mapping from $\mathrm{ XOR}$ to $\mathrm{ Majority}$ which has average stretch $O(\sqrt{ n})$, matching a previously known lower bound. (3) We give a 3-Lipschitz embedding $\phi : \{ 0,1\}^n \to \{ 0,1\}^{ 2n+1}$ such that $\mathrm{ XOR}(x) = \mathrm{ Majority}(\phi(x))$ for all $x \in \{ 0,1\}^n$. (4) We show that with high probability there is a $O(1)$-bi-Lipschitz mapping from $\mathrm{ Dictator}$ to a uniformly random balanced function.
Categories: math.CO cs.DM