Lipschitz bijections between boolean functions

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 , matching a previously known lower bound. (3) We give a 3-Lipschitz embedding such that for all . (4) We show that with high probability there is an O(1)-bi-Lipschitz mapping from Dictator to a uniformly random balanced function.