---
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 \in {{\mathbb N}}$ there exists an explicit bijection ${\psi}\colon \{0,1\}^n \to \left\{ x \in \{0,1\}^{n+1} \colon |x| > n/2 \right\}$ such that for every $x \neq y \in {\{0,1\}^{n}}$ it holds that $$\frac{1}{5}\leq \frac{{{\sf distance}}({\psi}(x),{\psi}(y))}{{{\sf distance}}(x,y)} \leq 4,$$ where ${{\sf 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 will require some new ideas beyond the sensitivity-based structural results of Boppana \[IPL 97\].

    We study the mapping ${\psi}$ further and show that it (and its inverse) are computable in DLOGTIME-uniform ${\mathbf{TC^{0}}}$, but not in ${\mathbf{AC^{0}}}$. Moreover, we prove that ${\psi}$ is “approximately local” in the sense that all but the last output bit of ${\psi}$ are essentially determined by a single input bit.
author:
- 'Itai Benjamini[^1]'
