On Lipschitz Bijections Between Boolean Functions

Abstract

Given two functions f,g : {0,1}ⁿ → {0,1}, a mapping ψ : {0,1}ⁿ → {0,1}ⁿ is said to be a mapping from f to g if it is a bijection and f(z) = g(ψ(z)) for every z ∈ {0,1}ⁿ. In this paper we study Lipschitz mappings between Boolean functions.

Our first result gives a construction of a C-Lipschitz mapping from the Majority function to the Dictator function for some universal constant C. On the other hand, there is no n/2-Lipschitz mapping in the other direction, namely from the Dictator function to the Majority function. This answers an open problem posed by Daniel Varga in the paper of Benjamini, Cohen and Shinkar (FOCS 2014 [1]).

We also show a mapping from Dictator to XOR that is 3-local, 2-Lipschitz, and its inverse is O(log(n))-Lipschitz, where by L-local mapping we mean that each output bit of the mapping depends on at most L input bits.

Next, we consider the problem of finding functions such that any mapping between them must have large average stretch, where the average stretch of a mapping φ is defined as

$${\sf avgstretch}(\phi) = {\mathbb E}_{x,i}[{\sf dist}(\phi(x),\phi(x+e_i)].$$

We show that any mapping φ from XOR to Majority must satisfy avgStretch(φ) ≥ c$\sqrt{n}$ for some absolute constant c > 0. In some sense, this gives a ‘function analogue’ to the question of Benjamini, Cohen and Shinkar (FOCS 2014 [1]), who asked whether there exists a set A ⊆ {0,1}ⁿ of density 0.5 such that any bijection from {0,1}ⁿ⁻¹ to A has large average stretch.

Finally, we show that for a random balanced function f: {0,1}ⁿ → {0,1}ⁿ, with high probability there is a mapping φ from Dictator to f such that both φ and φ⁻¹ have constant average stretch. In particular, this implies that one cannot obtain lower bounds on average stretch by taking uniformly random functions.