On Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings

Moses Charikar, Ofir Geri, Michael P. Kim +1

Edit distance is a fundamental measure of distance between strings and has been widely studied in computer science. While the problem of estimating edit distance has been studied e…