Low Distortion Embedding from Edit to Hamming Distance using Coupling.

The Hamming and the edit metrics are two common notions of measuring distances between pairs of strings x, y lying in the Boolean hypercube. The edit distance between x and y is de ned as the minimum number of character insertion, deletion, and bit ips needed for converting x into y. Whereas, the Hamming distance between x and y is the number of bit ips needed for converting x to y. In this paper we study a randomized injective embedding of the edit distance into the Hamming distance with a small distortion. This question was studied by Jowhari (ESA 2012) and is mainly motivated by two questions in communication complexity: the document exchange problem and deciding edit distance using a sketching protocol. We show a randomized embedding with quadratic distortion. Namely, for any x, y satisfying that their edit distance equals k, the Hamming distance between the embedding of x and y is O(k) with high probability. This improves over the distortion ratio of O(log n log∗ n) obtained by Jowhari for small values of k. Moreover, the embedding output size is linear in the input size and the embedding can be computed using a single pass over the input. ∗Department of Computer Science u0026 Engineering, Indian Institute of Technology Kanpur, Kanpur, India, diptarka@cse.iitk.ac.in. Work done while visiting Charles University in Prague. † Charles University in Prague, Computer Science Institute of Charles University, Malostranske namesti 25, 118 00 Praha 1, Czech Republic, elazargold@gmail.com. The research leading to these results has received funding from the European Research Council under the European Unionu0027s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement n. 616787. ‡Charles University in Prague, Computer Science Institute of Charles University, Malostranske namesti 25, 118 00 Praha 1, Czech Republic, koucky@iuuk.m .cuni.cz. The research leading to these results has received funding from the European Research Council under the European Unionu0027s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement n. 616787.