Bi-Lipschitz bijection between the Boolean cube and the Hamming ball

作者：Benjamini Itai^*; Cohen Gil; Shinkar Igor

来源：Israel Journal of Mathematics, 2016, 212(2): 677-703.

DOI：10.1007/s11856-016-1302-0

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 a N there exists an explicit bijection psi: {0, 1} (n) -> {x a {0, 1} (n+1) : |x| > n/2} such that for every x not equal y a {0, 1} (n) , where distance(center dot, center dot) 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 (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 (1997).
We study the mapping psi further and show that it (and its inverse) are computable in DLOGTIME-uniform TC0, but not in 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.

• 出版日期2016-5