This talk is a merge of two papers.
1: Constant-factor approximation of near-linear edit distance in near-linear time
Joshua Brakensiek (Stanford University), Aviad Rubinstein (Stanford University).
2: Constant factor approximations to edit distance on far input pairs in nearly linear time
Michal Koucky (Charles University, Prague), Michael Saks (Rutgers Unviersity).
