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 nN there exists an explicit bijection n/2 \right\}">:01nx01n+1:xn2 such that for every x=y01n it holds that51distance(xy)distance((x)(y))4where 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 further and show that it (and its inverse) are computable in DLOGTIME-uniform TC0, but not in AC0. Moreover, we prove that is ``approximately local'' in the sense that all but the last output bit of are essentially determined by a single input bit.