Sublinear Time Algorithms for Estimating Edit Distance

on YouTube ↗01h 08m

" summary

Distinguishes edit distance ≤k from >k^2 in sublinear time and gives concrete algorithms and limits: an adaptive route uses longest common extension queries and periodicity tests to reach runtimes like n/k + k^2 (previously n/k + k^3), with the polynomial-in-k cost coming from local k-sized probes to find periodic patterns; a non-adaptive multilayer block sampler runs in roughly n/√k (and matches a non-adaptive lower bound); proofs use Landau–Vishkin style banded DP reductions and randomized sampling and succeed with Monte‑Carlo guarantees.

AI-written summary · about

" chapters (11)

1. 0:00Introduction to sublinear algorithms
2. 2:58Defining the problem
3. 4:28Fundamentals of edit distance
4. 8:03The challenge of random sampling
5. 10:02History of gap edit distance
6. 16:04State of the art plot analysis
7. 22:13Technique development
8. 27:37Landu-Vishkin algorithm basics
9. 38:52Adaptivity and periodicity
10. 50:31Non-adaptive sampling methods
11. 59:37Future directions and conclusion

" related talks

• 01h 09mSketching High-Dimensional DataJelani Nelson · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 35mSampling for Subset Selection and ApplicationsAmit Deshpande · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 01h 13mSketching High-Dimensional DataJelani Nelson · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 01h 24mStreaming, Sketching and Sufficient Statistics IGraham Cormode · Big Data Boot Camp 2013
• 01h 26mStreaming, Sketching and Sufficient Statistics IIGraham Cormode · Big Data Boot Camp 2013
• 43mSub-Quadratic Recovery of Correlated PairsGraham Cormode · Real-Time Decision Making
• 32mStreaming Algorithms for Matchings in Low Arboricity GraphsSofya Vorotnikova · Real-Time Decision Making 2018
• 48mHomomorphic Sketches: Shrinking Big Data without Sacrificing StructureAndrew McGregor · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)