Lipschitz bijections between boolean functions
22nd October 2019, 11:00 am – 12:00 pm
Fry Building, 2.04
A frequent theme in the analysis of boolean functions is the study of the similarities and differences between boolean functions with different geometric or structural properties; for example, between functions such as Dictator that are determined by a small number of coordinates, and functions such as Majority or XOR that are not. One measure of similarity, introduced by Rao and Shinkar in 2018, is the existence of a Lipschitz mapping (with small constant) between them.
In this talk, we answer two questions posed by Rao and Shinkar.
- 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.
- We show that with high probability there is a O(1)-bi-Lipschitz mapping from
Dictator to a uniformly random balanced function.
Joint work with Alex Scott.