Constant factor approximations to edit distance on far input pairs in nearly linear time

Michal Koucký, Michael Saks

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

Abstract

For any T ≥ 1, there are constants R=R(T) ≥ 1 and ζ=ζ(T)>0 and a randomized algorithm that takes as input an integer n and two strings x,y of length at most n, and runs in time O(n1+1/T) and outputs an upper bound U on the edit distance of edit(x,y) that with high probability, satisfies U ≤ R(edit(x,y)+n1-ζ). In particular, on any input with edit(x,y) ≥ n1-ζ the algorithm outputs a constant factor approximation with high probability. A similar result has been proven independently by Brakensiek and Rubinstein (this proceedings).

Original languageEnglish (US)
Title of host publicationSTOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
EditorsKonstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, Julia Chuzhoy
PublisherAssociation for Computing Machinery
Pages699-712
Number of pages14
ISBN (Electronic)9781450369794
DOIs
StatePublished - Jun 8 2020
Event52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 - Chicago, United States
Duration: Jun 22 2020Jun 26 2020

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020
Country/TerritoryUnited States
CityChicago
Period6/22/206/26/20

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Almost linear-time algorithm
  • Approximation algorithm
  • Edit distance
  • Randomized algorithm

Cite this