Constant Factor Approximations to Edit Distance in Nearly Linear Time

Constant Factor Approximations to Edit Distance in Nearly Linear Time

Explore constant factor approximations to edit distance in nearly linear time through this 24-minute conference talk merging two papers. Delve into the main results and approximation techniques for edit distance. Learn about partitioning strings into windows, reducing to non-crossing matching, and handling dense graphs using triangle inequality. Discover methods for sparse graphs via "seed-and-expand" and union of disjoint bl-cliques. Examine searching for matches in both sparse and dense cases using the CDGKS algorithm. Investigate multiple levels in the sparse case and recap the key concepts presented by researchers from Stanford University, Charles University, and Rutgers University.