Johnson and Lindenstrauss lemma for hamming space

Question

A result of Johnson and Lindenstrauss shows that a set of $n$ points in high dimensional Euclidean space can be mapped into an $O(\frac{\log n}{\epsilon^2})$- dimensional Euclidean space such that the distance between any two points changes by only a factor of $(1\pm \epsilon).$

I am looking for reference for a similar result for Hamming space- i.e. a set of $n$ binary vectors can be mapped into a very low dimensional space such that the hamming distance between any pair of vectors is approximately preserved.

Answer 1

Consider the $n$ vectors $e_1,\ldots,e_n$ of weight $1$, and the zero vector $e_0$. The Hamming distance between $e_0$ to any $e_i$ is $1$. Let $\varphi$ be a map into a Hamming cube of dimension $m$, and suppose that it preserves distances up to a factor of $C$. In particular, the $n$ points $\varphi(e_1),\ldots,\varphi(e_n)$ are within distance $C$ of $\varphi(e_0)$. On the other hand, the number of points at distance at most $C$ from $\varphi(e_0)$ is $O(m^C)$. We conclude that $m = \Omega(n^{1/C})$ is polynomial in $n$ rather than logarithmic in $n$.