We present a near-linear time algorithm that approximates the edit distance between two strings within a polylogarithmic factor. For strings of length n and every fixed ε > 0, the algorithm computes a (log n) O(1/ε) approximation in n 1+ε time. This is an exponential improvement over the previously known approximation factor, 2Õ ( √ log n) , with a comparable running time [Ostrovsky and Rabani, J. ACM 2007; Andoni and Onak, STOC 2009]. This result arises naturally in the study of a new asymmetric query model. In this model, the input consists of two strings x and y, and an algorithm can access y in an unrestricted manner, while being charged for querying every symbol of x. Indeed, we obtain our main result by designing an algorithm that makes a small number of queries in this model. We then provide a nearly-matching lower bound on the number of queries. Our lower bound is the first to expose hardness of edit distance stemming from the input strings being "repetitive", which means that many of their substrings are approximately identical. Consequently, our lower bound provides the first rigorous separation between edit distance and Ulam distance. 1 The result of [26] applies to constant-size alphabets. It was extended to arbitrarily large alphabets in [11] , albeit with an O(log log n) 2 factor loss in runtime. 2 We shall not attempt to present a complete list of results for restricted settings (e.g., average-case/smoothed analysis, weaklyrepetitive strings, and bounded distance-regime), for variants of the distance function (e.g., allowing more edit operations), or for related computational problems (such as pattern matching, nearest neighbor search, and sketching). See also the surveys of [29] and [31] .
For string edit distance, the current best approximation ratio of (log n) O( 1 ) in n 1+ running time for any fixed > 0 is due to Andoni, Krauthgamer and Onak REF .
Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
2010 IEEE 51st Annual Symposium on Foundations of Computer Science
2010 IEEE 51st Annual Symposium on Foundations of Computer Science
Computer Science Mathematics