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
|
| _version_ | 1797070844057354240 |
|---|---|
| author | Johnston, T Scott, A |
| author_facet | Johnston, T Scott, A |
| author_sort | Johnston, T |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T22:44:49Z |
| format | Journal article |
| id | oxford-uuid:5cce255b-381f-490b-aa60-7fd6817c1bc3 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T22:44:49Z |
| publishDate | 2020 |
| publisher | Cambridge University Press |
| record_format | dspace |
| spelling | oxford-uuid:5cce255b-381f-490b-aa60-7fd6817c1bc32022-03-26T17:30:28ZLipschitz bijections between boolean functionsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:5cce255b-381f-490b-aa60-7fd6817c1bc3EnglishSymplectic ElementsCambridge University Press2020Johnston, TScott, AWe 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. |
| spellingShingle | Johnston, T Scott, A Lipschitz bijections between boolean functions |
| title | Lipschitz bijections between boolean functions |
| title_full | Lipschitz bijections between boolean functions |
| title_fullStr | Lipschitz bijections between boolean functions |
| title_full_unstemmed | Lipschitz bijections between boolean functions |
| title_short | Lipschitz bijections between boolean functions |
| title_sort | lipschitz bijections between boolean functions |
| work_keys_str_mv | AT johnstont lipschitzbijectionsbetweenbooleanfunctions AT scotta lipschitzbijectionsbetweenbooleanfunctions |