Lipschitz bijections between boolean functions
share
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 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(√(n)), matching a previously known lower bound. (3) We give a 3-Lipschitz embedding ϕ : {0,1}^n →{0,1}^2n+1 such that XOR(x) = Majority(ϕ(x)) for all x ∈{0,1}^n. (4) We show that with high probability there is a O(1)-bi-Lipschitz mapping from Dictator to a uniformly random balanced function.
READ FULL TEXT