4 citations · 10 across the 14 of their papers we have counts for
Showing 2019Show all
2 papers · 1 filter
cs.DS2019★ 3 cited
Reducing approximate Longest Common Subsequence to approximate Edit Distance
Aviad Rubinstein, Zhao Song
Given a pair of strings, the problems of computing their Longest Common Subsequence and Edit Distance have been extensively studied for decades. For exact algorithms, LCS and Edit…
cs.DS2019
Constant-factor approximation of near-linear edit distance in near-linear time
Joshua Brakensiek, Aviad Rubinstein
We show that the edit distance between two strings of length can be computed within a factor of in time as long as the edit distance is at least for…