Finding the length of the longest increasing subsequence (LIS) is a classic algorithmic problem. Let @math denote the size of the array. Simple @math algorithms are known for this problem. We develop a polylogarithmic time randomized algorithm that for any constant @math , estimates the length of the LIS of an array to within an additive error of @math . More precisely, the running time of the algorithm is @math where the exponent @math is independent of @math . Previously, the best known polylogarithmic time algorithms could only achieve an additive @math approximation. With a suitable choice of parameters, our algorithm also gives, for any fixed @math , a multiplicative @math -approximation to the distance to monotonicity @math (the fraction of entries not in the LIS), whose running time is polynomial in @math and @math . The best previously known algorithm could only guarantee an approximation within a factor (arbitrarily close to) 2.
There has been a body of work on studying the Ulam distance between strings @cite_15 @cite_1 @cite_20 @cite_10 . For permutations, the Ulam distance is twice the size of the complement of the longest common subsequence. Note that Ulam distance between a permutation and the identity permutation is basically the distance to monotonicity. There has been a recent sublinear time algorithm for approximating the Ulam distance between two permutations @cite_10 . We again note that the previous techniques for distance approximation play a role in these results. Our results may be helpful in getting better approximations for these problems.
@cite_10 @cite_15 @cite_1 @cite_20
2076238476 2046785857 2169838205 2012010763
We initiate the study of the smoothed complexity of sequence alignment, by proposing a semi-random model of edit distance between two input strings, generated as follows: First, an adversary chooses two binary strings of length d and a longest common subsequence A of them. Then, every character is perturbed independently with probability p, except that A is perturbed in exactly the same way inside the two strings. We design two efficient algorithms that compute the edit distance on smoothed instances up to a constant factor approximation. The first algorithm runs in near-linear time, namely d 1+e for any fixed e > 0. The second one runs in time sublinear in d, assuming the edit distance is not too small. These approximation and runtime guarantees are significantly better than the bounds that were known for worst-case inputs. Our technical contribution is twofold. First, we rely on finding matches between substrings in the two strings, where two substrings are considered a match if their edit distance is relatively small, a prevailing technique in commonly used heuristics, such as PatternHunter of [2002]. Second, we effectively reduce the smoothed edit distance to a simpler variant of (worst-case) edit distance, namely, edit distance on permutations (a.k.a. Ulam's metric). We are thus able to build on algorithms developed for the Ulam metric, whose much better algorithmic guarantees usually do not carry over to general edit distance. We give near-tight bounds for estimating the edit distance between two non-repetitive strings (Ulam distance) with constant approximation, in sub-linear time. For two strings of length d and at edit distance R, our algorithm runs in time O(d R + √d) and outputs a constant approximation to R. We also prove a matching lower bound (up to logarithmic terms). Both upper and lower bounds are improvements over previous results from, respectively, [Andoni-Indyk-Krauthgamer, SODA'09] and [Batu-Ergun-Kilian-Magen-Raskhodnikova-Rubinfeld-Sami, STOC'03]. We prove the first nontrivial communication complexity lower bound for the problem of estimating the edit distance (aka Levenshtein distance) between two strings. To the best of our knowledge, this is the first computational setting in which the complexity of estimating the edit distance is provably larger than that of Hamming distance. Our lower bound exhibits a trade-off between approximation and communication, asserting, for example, that protocols with @math bits of communication can obtain only approximation @math , where @math is the length of the input strings. This case of @math communication is of particular importance since it captures constant-size sketches as well as embeddings into spaces like @math and squared- @math , two prevailing algorithmic approaches for dealing with edit distance. Indeed, the known nontrivial communication upper bounds are all derived from embeddings into @math . By excluding low-communication protocols for edit distance, we rule out a strictly richer class of algorithms than previous results. Furthermore, our lower bound holds not only for strings over a binary alphabet but also for strings that are permutations (aka the Ulam metric). For this case, our bound nearly matches an upper bound known via embedding the Ulam metric into @math . Our proof uses a new technique that relies on Fourier analysis in a rather elementary way. The edit distance between two character strings can be defined as the minimum cost of a sequence of editing operations which transforms one string into the other. The operations we admit are deleting, inserting and replacing one symbol at a time, with possibly different costs for each of these operations. The problem of finding the longest common subsequence of two strings is a special case of the problem of computing edit distances. We describe an algorithm for computing the edit distance between two strings of length n and m, n ⪖ m, which requires O(n · max(1, mlog n)) steps whenever the costs of edit operations are integral multiples of a single positive real number and the alphabet for the strings is finite. These conditions are necessary for the algorithm to achieve the time bound.