Approximating Edit Distance in the Fully Dynamic Model
summary
Presents a dynamic algorithm that approximates edit distance with amortized update time n^ε (for any ε>0) at a polylog(n) approximation factor, trading off arity and depth of a precision-sampling tree. Uses capped tree distance (AKO 2010 style), shift sparsification and active-node pruning to reduce affected nodes after substitutions or a single insertion/deletion in Y, maintains LCE-like structure on X, and gives expected-time guarantees; constant-factor in n^ε remains open.
AI-written summary · about
chapters (16)
- 0:00Introduction
- 1:55What is Edit Distance
- 4:35Dynamic Model
- 5:55What is known
- 7:15Approximating Edit Distance
- 15:17Can we do better
- 17:05Highlevel ideas
- 23:26Tree distance
- 25:27Capped tree distance
- 27:48Additive approximation
- 31:26Precision sampling limit
- 35:03Active node
- 37:49Substitutions
- 42:22Substitutions in Y
- 43:50More ideas
- 48:07Summary