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

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 $\mathrm{distance}(x,y) / 5 \leq \mathrm{distance}(f(x),f(y)) \leq 4\, \mathrm{distance}(x,y)$ where $\mathrm{distance}(\cdot,\cdot)$ 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 requires ideas beyond the sensitivity-based structural results of Boppana [IPL 97]. No prior knowledge is assumed. Joint work with Itai Benjamini and Igor Shinkar.