Lipschitz bijections between boolean functions

Source abstract

Abstract We answer four questions from a recent paper of Rao and Shinkar [17] 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 Dictator to XOR such that each output bit depends on O (1) input bits. (2) We give a construction for a mapping from XOR to Majority which has average stretch $O(\sqrt{n})$ , matching a previously known lower bound. (3) We give a 3-Lipschitz embedding $\phi \colon \{0,1\}^n \to \{0,1\}^{2n+1}$ such that $${\rm{XOR }}(x) = {\rm{ Majority }}(\phi (x))$$ for all $x \in \{0,1\}^n$ . (4) We show that with high probability there is an O (1)-bi-Lipschitz mapping from Dictator to a uniformly random balanced function.