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...
| Principais autores: | , |
|---|---|
| Formato: | Journal article |
| Idioma: | English |
| Publicado em: |
Cambridge University Press
2020
|
| Resumo: | 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. |
|---|