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.

Syllabus

Intro
Approx ED
Main Result
Approximating ED
Partition strings into windows
Step 0: Reduction to non-crossing matching
Note: this step crucially uses triangle inequality!
Step 1: Dense graphs via triangle inequality
Sparse graphs via "seed-and-expand"
Union of disjoint bl-cliques
Searching for matches [KS]
Sparse case CDGKS
Dense case CDGKS
Multiple levels - sparse case [KS]
Recap