Before revision:  This generalizes the linear-time embedding of Chakraborty, Goldenberg, Koucky, STOC 2016], where the resultant Hamming distance is between k and k^2 . Our algorithm is based on a random walk over samples, which we believe will find other applications in sublinear-time algorithms.
After revision:  This generalizes the linear-time embedding of Chakraborty, Goldenberg, Koucky, STOC 2016], where the resultant Hamming distance is between \frac k2 and O(k^2) . Our algorithm is based on a random walk over samples, which we believe will find other applications in sublinear-time algorithms.