Journal article
Lipschitz bijections between boolean functions
- 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 , 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, 303.4KB, Terms of use)
-
- Publisher copy:
- 10.1017/S0963548320000541
Authors
- Publisher:
- Cambridge University Press
- Journal:
- Combinatorics Probability and Computing More from this journal
- Volume:
- 30
- Issue:
- 4
- Pages:
- 513-525
- Publication date:
- 2020-11-16
- Acceptance date:
- 2019-05-30
- DOI:
- EISSN:
-
1469-2163
- ISSN:
-
0963-5483
- Language:
-
English
- Keywords:
- Pubs id:
-
990667
- Local pid:
-
pubs:990667
- Deposit date:
-
2021-01-09
Terms of use
- Copyright holder:
- Johnston and Scott
- Copyright date:
- 2020
- Rights statement:
- © The Author(s), 2020. Published by Cambridge University Press.
- Notes:
- This is the accepted manuscript version of the article. The final version is available online from Cambridge University Press at: https://doi.org/10.1017/S0963548320000541
If you are the owner of this record, you can report an update to it here: Report update to this record