Thomas Johnston

University of Oxford

Lipschitz bijections between boolean functions

Combinatorics Seminar

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.

Organisers: David Ellis, Tom Johnston

Comments are closed.