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:  Our \tilde{O}(\frac{n}{p})-time procedure yields an embedding with distortion O(kp) , where k is the edit distance of the original strings.