Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball
Itaï Benjamini, Gil Cohen, Igor Shinkar · 2014
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 E N there exists an explicit bijection ψ: {0, 1}n→ {x E {0, 1}n+1 : |x| > n/2} such that for every x ≠ y E {0, 1}n+1it holds that 1/5 ≤ dist(ψ(x), ψ(y)) ≤ 4 5 - dist(x, y) where dist(·, ·) 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]. We study the mapping ψ further and show that it (and its inverse) are computable in DLOGTIME-uniform TC°, but not in AC°. 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.