Constant Factor Approximations to Edit Distance in Nearly Linear Time

Constant Factor Approximations to Edit Distance in Nearly Linear Time

Association for Computing Machinery (ACM) via YouTube Direct link

Main Result

3 of 15

3 of 15

Main Result

Class Central Classrooms beta

YouTube videos curated by Class Central.

Classroom Contents

Constant Factor Approximations to Edit Distance in Nearly Linear Time

Automatically move to the next video in the Classroom when playback concludes

  1. 1 Intro
  2. 2 Approx ED
  3. 3 Main Result
  4. 4 Approximating ED
  5. 5 Partition strings into windows
  6. 6 Step 0: Reduction to non-crossing matching
  7. 7 Note: this step crucially uses triangle inequality!
  8. 8 Step 1: Dense graphs via triangle inequality
  9. 9 Sparse graphs via "seed-and-expand"
  10. 10 Union of disjoint bl-cliques
  11. 11 Searching for matches [KS]
  12. 12 Sparse case CDGKS
  13. 13 Dense case CDGKS
  14. 14 Multiple levels - sparse case [KS]
  15. 15 Recap

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.