Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball

by Itai Benjamini, Gil Cohen, and Igor Shinkar

Oded's comments

I find the question very interesting, regardless of the authors original motivation. Indeed, the common wisdom is that the Hamming Ball (i.e., the set of $n+1$-bit strings with majority of 1-entries) and Boolean Cube (i.e., the set of $n$-bit strings) are very different, and one might have expect to have no bi-Lipschitz bijection between them. Still, this work shows that such a (relatively simple) bijection does exist. It raises the question of whether there exists such bijections between almost all elements of every two sets of equal constant density; that is, for every two sets $A,B\subset\{0,1\}^n$ of cardinality (say) $2^{n-1}$, is there a bi-Lipschitz bijection between some $A'\subset A$ and $B'\subset B$ that are each of size (say) $2^{n-2}$?

Note by Igor (23-6-14): The choice of parameters for the open problem is unfortunatelty not a good one; that is, if each set has density $\rho$ and the desired subsets are only required to be of density $\rho^2$, then a simple solution exists: For a random $r$, it holds that $E_r[|(A+r)\cap B|]=|A|\cdot|B|/2^n$, and so there exists an $r$ s.t. $B'=(A+r)\cap B$ has density $\rho^2$ and the mapping $x\mapsto x+r$ is isometric from $A'=B'-x$ to $B'$.
Note by Oded: Indeed, let's change the concrete challenge as follows. For every two sets $A,B\subset\{0,1\}^n$ of cardinality $2^{n-5}$, is there a bi-Lipschitz bijection between some $A'\subset A$ and $B'\subset B$ that are each of size $2^{n-6}$?

The original abstract

We construct a bi-Lipschitz bijection from the Boolean cube to the Hamming ball of equal volume. More precisely, we show that for all even n there exists an explicit bijection $f$ from the n-dimensional Boolean cube to the Hamming ball of equal volume embedded in $(n+1)$-dimensional Boolean cube, such that for all $x$ and $y$ it holds that distance $(x,y) / 5 <=$ distance $(f(x),f(y)) <= 4$ distance $(x,y)$, where distance $(,)$ denotes the Hamming distance. In particular, this implies that the Hamming ball is bi-Lipschitz transitive.

This result gives a strong negative answer to an open problem of Lovett and Viola (CC 2012), who raised the question in the context of sampling distributions in low-level complexity classes. The conceptual implication is that the problem of proving lower bounds in the context of sampling distributions will require some new ideas beyond the sensitivity-based structural results of Boppana (IPL 97).

We study the mapping $f$ further and show that it (and its inverse) are computable in DLOGTIME-uniform TC0, but not in AC0. Moreover, we prove that $f$ is "approximately local" in the sense that all but the last output bit of $f$ are essentially determined by a single input bit.


Back to list of Oded's choices.