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...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Cambridge University Press
2020
|