Efficient Communication Protocols for Deciding Edit Distance

In this paper we present two communication protocols on computing edit distance. In our first result, we give a one-way protocol for the following Document Exchange problem. Namely given x is an element of Sigma(n) to Alice and y is an element of Sigma(n) to Bob and integer k to both, Alice sends a message to Bob so that he learns x or truthfully reports that the edit distance between x and y is greater than k. For this problem, we give a randomized protocol in which Alice transmits at most (O) over tilde (k log(2) n) bits and each party's time complexity is (O) over tilde (n log n + k(2) log(2) n). Our second result is a simultaneous protocol for edit distance over permutations. Here Alice and Bob both send a message to a third party (the referee) who does not have access to the input strings. Given the messages, the referee decides if the edit distance between x and y is at most k or not. For this problem we give a protocol in which Alice and Bob run a O(n log n)-time algorithm and they transmit at most (O) over tilde (k log(2) n) bits. The running time of the referee is bounded by (O) over tilde (k(2) log(2) n). To our knowledge, this result is the first upper bound for this problem. Our results are obtained through mapping strings to the Hamming cube. For this, we use the Locally Consistent Parsing method of [5,6] in combination with the Karp-Rabin fingerprints. In addition to yielding non-trivial bounds for the edit distance problem, this paper suggest a new conceptual framework and raises new questions regarding the embeddability of edit distance into the Hamming cube which might be of independent interest.