Before revision:  Our \tilde{O}(\frac{n}{p})-time procedure yields an embedding with distortion k^2p , where k is the edit distance of the original strings.
After revision:  For any parameter p, our \tilde{O}(\frac{n}{p})-time procedure yields an embedding with distortion k^2p , where k is the edit distance of the original strings.