ECCC-Report TR13-138https://eccc.weizmann.ac.il/report/2013/138Comments and Revisions published for TR13-138en-usThu, 31 Oct 2013 20:16:07 +0200
Revision 1
| Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball |
Itai Benjamini,
Gil Cohen,
Igor Shinkar
https://eccc.weizmann.ac.il/report/2013/138#revision1We 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.Thu, 31 Oct 2013 20:16:07 +0200https://eccc.weizmann.ac.il/report/2013/138#revision1
Paper TR13-138
| Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball |
Itai Benjamini,
Gil Cohen,
Igor Shinkar
https://eccc.weizmann.ac.il/report/2013/138We 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.Tue, 08 Oct 2013 08:40:19 +0300https://eccc.weizmann.ac.il/report/2013/138