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{distance(\psi(x),\psi(y))}{distance(x,y)} \leq 4,
\]
where $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.

Mainly added a reference communicated to us by Viola.

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{distance(\psi(x),\psi(y))}{distance(x,y)} \leq 4,
\]
where $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.