Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-138 | 31st October 2013 20:16

Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball

RSS-Feed




Revision #1
Authors: Itai Benjamini, Gil Cohen, Igor Shinkar
Accepted on: 31st October 2013 20:16
Downloads: 1813
Keywords: 


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{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.



Changes to previous version:

Mainly added a reference communicated to us by Viola.


Paper:

TR13-138 | 5th October 2013 15:45

Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball





TR13-138
Authors: Itai Benjamini, Gil Cohen, Igor Shinkar
Publication: 8th October 2013 08:40
Downloads: 4482
Keywords: 


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{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.



ISSN 1433-8092 | Imprint