Edit distance is one of the most fundamental problems in combinatorial optimization to measure the similarity between strings. Ulam distance is a special case of edit distance where no character is allowed to appear more than once in a string. Recent developments have been very fruitful for obtaining fast and parallel algorithms for both edit distance and Ulam distance. In this work, we present an almost optimal MPC (massively parallel computation) algorithm for Ulam distance and improve MPC algorithms for edit distance. Our algorithm for Ulam distance is almost optimal in the sense that (1) the approximation factor of our algorithm is 1+ε1+ε, (2) the round complexity of our algorithm is constant, (3) the total memory of our algorithm is almost linear (~Oε(n)Õε(n)), and (4) the overall running time of our algorithm is almost linear which is the best known for Ulam distance. We also improve the work of Hajiaghayi et al. for edit distance in terms of total memory. The best previously known MPC algorithm for edit distance requires ~O(n2x)Õ(n2x) machines when the memory of each machine is bounded by ~O(n1-x)Õ(n1-x). In this work, we improve the number of machines to ~O(n(9/5)x)Õ(n(9/5)x) while keeping the memory limit intact. Moreover, the round complexity of our algorithm is constant and the total running time of our algorithm is truly subquadratic. However, our improvement comes at the expense of a constant factor in the approximation guarantee of the algorithm. This improvement is inspired by the recent techniques of Boroujeni et al. and Chakraborty et al. for obtaining truly subquadratic time algorithms for edit distance.

Edit distance and longest common subsequence are among the most fundamental problems in combinatorial optimization. Recent developments have proven strong lower bounds against subquadratic time solutions for both problems. Moreover, the best approximation factors for subquadratic time solutions have been limited to 3 for edit distance and super constant for longest common subsequence. Improved approximation algorithms for these problems1 are some of the biggest open questions in combinatorial optimization. In this work, we present improved algorithms for both edit distance and longest common subsequence. The running times are truly subquadratic, though we obtain 1 + o(1) approximate solutions for both problems if the input satisfies a mild condition. In this setting, first, an adversary chooses one of the input strings. Next, this string is perturbed by a random procedure, and then the adversary chooses the second string after observing the perturbed one.

Edit distance is one of the most fundamental problems in combinatorial optimization. Ulam distance is a special case of edit distance where no character is allowed to appear more than once in a string. Recent developments have been very fruitful for obtaining fast and parallel algorithms for both edit distance and Ulam distance. In this work, we present an almost optimal MPC algorithm for Ulam distance and improve MPC algorithms for edit distance. Our algorithm for Ulam distance is optimal in the sense that (1) the approximation factor of our algorithm is 1+ε, (2) the round complexity of our algorithm is constant, (3) the total memory of our algorithm is almost linear (~O(n)), and (4) the overall running time of our algorithm is almost linear which is the best known for Ulam distance. Similar to edit distance and longest common subsequence (LCS) which are considered as dual problems, Ulam distance and longest increasing subsequence (LIS) are also seen as dual problems. LIS is equivalent to a special case of LCS where each string can contain each character at most once. In that sense, our result for Ulam distance complements the work of Im et al., wherein a similar result is presented for łis. We also improve the work of Hajiaghayi et al. for edit distance in terms of total memory. The best previously known MPC algorithm for edit distance requires ~O(n2x) machines when the memory of each machine is bounded by ~O(n1-x). In this work, we improve the number of machines to ~O(n1.75x) while keeping the memory limit intact. Moreover, the round complexity of our algorithm is constant and the total running time of our algorithm is truly subquadratic. However, our improvement comes at the expense of a constant factor in the approximation guarantee of the algorithm. This improvement is inspired by the recent techniques of Boroujeni et al. and Chakraborty et al. for obtaining truly subquadratic time algorithms for edit distance.

Edit distance is one of the most fundamental problems in computer science. Tree edit distance is a natural generalization of edit distance to ordered rooted trees. Such a generalization extends the applications of edit distance to areas such as computational biology, structured data analysis (e.g., XML), image analysis, and compiler optimization. Perhaps the most notable application of tree edit distance is in the analysis of RNA molecules in computational biology where the secondary structure of RNA is typically represented as a rooted tree.

The edit distance between two strings is defined as the smallest number of insertions, deletions, and substitutions that need to be made to transform one of the strings to another one. Approximating edit distance in subquadratic time is “one of the biggest unsolved problems in the field of combinatorial pattern matching” [21]. Our main result is a quantum constant approximation algorithm for computing the edit distance in truly subquadratic time. More precisely, we give an O(n1.858) quantum algorithm that approximates the edit distance within a factor of 7. We further extend this result to an O(n1.781) quantum algorithm that approximates the edit distance within a larger constant factor. Our solutions are based on a framework for approximating edit distance in parallel settings. This framework requires as black box an algorithm that computes the distances of several smaller strings all at once. For a quantum algorithm, we reduce the black box to metric estimation and provide efficient algorithms for approximating it. We further show that this framework enables us to approximate edit distance in distributed settings. To this end, we provide a MapReduce algorithm to approximate edit distance within a factor of 3, with sublinearly many machines and sublinear memory. Also, our algorithm runs in a logarithmic number of rounds.