More Web Proxy on the site http://driver.im/

research-article

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

Authors:

Michal Koucký,

Michael SaksAuthors Info & Claims

STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

Pages 699 - 712

https://doi.org/10.1145/3357713.3384307

Published: 22 June 2020 Publication History

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(n ^1+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)+n ^1−ζ). In particular, on any input with edit(x,y) ≥ n ^1−ζ the algorithm outputs a constant factor approximation with high probability. A similar result has been proven independently by Brakensiek and Rubinstein (this proceedings).

References

[1]

Amir Abboud and Arturs Backurs. 2017. Towards Hardness of Approximation for Polynomial Time Problems. In 8th Innovations in Theoretical Computer Science Conference, ITCS 2017. 11 : 1-11 : 26.

[2]

Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. 2015. Tight Hardness Results for LCS and Other Sequence Similarity Measures. In Prof. of the IEEE Annual Symp. on Found. of Comp. Sci., FOCS 2015. 59-78.

[3]

Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams. 2016. Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made. In Proc. of the Annual ACM Symp. on Theory of Comp., STOC 2016. 375-388.

Digital Library

[4]

Alex Andoni. 2018. Simpler Constant-Factor Approximation to Edit Distance Problems. Manuscript ( 2018 ).

[5]

Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak. 2010. Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. In Proc. of the Annual IEEE Symp. on Found. of Comp. Sci., FOCS 2010. 377-386.

Digital Library

[6]

Alexandr Andoni and Krzysztof Onak. 2009. Approximating Edit Distance in Near-linear Time. In Proc. of the Forty-first Annual ACM Symp. on Theory of Comp. (Bethesda, MD, USA) ( STOC '09). ACM, 199-204.

Digital Library

[7]

Arturs Backurs and Piotr Indyk. 2015. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False). In Proc. of the Annual ACM on Symp. on Theory of Comp. (Portland, Oregon, USA) ( STOC '15). ACM, 51-58.

Digital Library

[8]

Z. Bar-Yossef, T.S. Jayram, R. Krauthgamer, and R. Kumar. 2004. Approximating edit distance eficiently. In Proc. of the Annual IEEE Symp. on Found. of Comp. Sci., FOCS 2004. 550-559.

[9]

Tugkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, and Rahul Sami. 2003. A Sublinear Algorithm for Weakly Approximating Edit Distance. In Proc. of the Annual ACM Symp. on Theory of Comp. (San Diego, CA, USA) ( STOC '03). ACM, 316-324.

Digital Library

[10]

Tuğkan Batu, Funda Ergun, and Cenk Sahinalp. 2006. Oblivious String Embeddings and Edit Distance Approximations. In Proc. of the Annual ACM-SIAM Symp. on Discrete Algorithm (Miami, Florida) (SODA '06). Society for Industrial and Applied Mathematics, 792-801.

[11]

Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, and Saeed Seddighin. 2018. Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce. In Proc. of the Annual ACM-SIAM Symp. on Discrete Algorithms, SODA 2018. 1170-1189.

[12]

Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, and Saeed Seddighin. 2018. Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce (extended version of ). ( 2018 ).

[13]

Joshua Brakensiek and Aviad Rubinstein. 2020. Constant-factor approximation of near-linear edit distance in near-linear time. Proc. of the ACM Symp. on Theory of Comp., STOC 2020.

Digital Library

[14]

Karl Bringmann and Marvin Künnemann. 2015. Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. In Prof. of the IEEE Annual Symp. on Found. of Comp. Sci., FOCS 2015. 79-97.

[15]

Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, and Michael E. Saks. 2018. Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time. In Prof. of the IEEE Annual Symp. on Found. of Comp. Sci., FOCS 2018. 979-990.

[16]

Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, and Michael E. Saks. 2018. Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time. CoRR abs/ 1810.03664 ( 2018 ). arXiv: 1810.03664 http://arxiv.org/abs/ 1810.03664

[17]

Diptarka Chakraborty, Debarati Das, and Michal Koucký. 2019. Approximate Online Pattern Matching in Sublinear Time. In Proc. of FSTTCS 2019 (LIPIcs), Vol. 150. 10: 1-10 : 15.

[18]

Elazar Goldenberg, Robert Krauthgamer, and Barna Saha. 2019. Sublinear Algorithms for Gap Edit Distance. In Proc. of the Annual IEEE Symp. on Found. of Comp. Sci., FOCS 2019. 1101-1120.

[19]

Szymon Grabowski. 2016. New tabulation and sparse dynamic programming based techniques for sequence similarity problems. Discrete Applied Mathematics 212 ( 2016 ), 96-103.

[20]

Gad M. Landau, Eugene W. Myers, and Jeanette P. Schmidt. 1998. Incremental String Comparison. SIAM J. Comput. 27, 2 (April 1998 ), 557-582.

[21]

VI Levenshtein. 1966. Binary Codes Capable of Correcting Deletions, Insertions and Reversals. Soviet Physics Doklady 10 ( 1966 ), 707.

[22]

William J. Masek and Michael S. Paterson. 1980. A faster algorithm Comp. string edit distances. J. Comput. System Sci. 20, 1 ( 1980 ), 18-31.

[23]

Esko Ukkonen. 1985. Algorithms for Approximate String Matching. Inf. Control 64, 1-3 ( March 1985 ), 100-118.

Digital Library

[24]

Robert A. Wagner and Michael J. Fischer. 1974. The String-to-String Correction Problem. J. ACM 21, 1 (Jan. 1974 ), 168-173.

Digital Library

Cited By

Koucký MSaks MMohar BShinkar IO'Donnell R(2024)Almost Linear Size Edit Distance SketchProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649783(956-967)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649783
Qi CLaili YRen LZhang LLi B(2024)A template augmented distant supervision framework for Chinese named entity recognitionInternational Journal of Modeling, Simulation, and Scientific Computing10.1142/S179396232450018115:01Online publication date: 19-Jan-2024
https://doi.org/10.1142/S1793962324500181
Bhattacharya SKoucký MSaha BServedio R(2023)Locally Consistent Decomposition of Strings with Applications to Edit Distance SketchingProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585239(219-232)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585239
Show More Cited By

Index Terms

Constant factor approximations to edit distance on far input pairs in nearly linear time
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Almost-optimal sublinear-time edit distance in the low distance regime
STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

We revisit the task of computing the edit distance in sublinear time. In the (k,K)-gap edit distance problem we are given oracle access to two strings of length n and the task is to distinguish whether their edit distance is at most k or at least K. It ...
Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time

Edit distance is a measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a dynamic ...
Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce
The edit distance between two strings is defined as the smallest number of insertions, deletions, and substitutions that need to be made to transform one of the strings to another one. Approximating edit distance in subquadratic time is “one of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

June 2020

1429 pages

ISBN:9781450369794

DOI:10.1145/3357713

General Chairs:
Konstantin Makarychev
Northwestern University, USA
,
Yury Makarychev
Toyota Technological Institute at Chicago, USA
,
Madhur Tulsiani
Toyota Technological Institute at Chicago, USA
,
Gautam Kamath
University of Waterloo, Canada
,
Program Chair:
Julia Chuzhoy
Toyota Technological Institute at Chicago, USA

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Simons Foundation
Grantová Agentura ðeské Republiky
European Research Council

Conference

STOC '20

Sponsor:

SIGACT

STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing

June 22 - 26, 2020

IL, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
138
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Koucký MSaks MMohar BShinkar IO'Donnell R(2024)Almost Linear Size Edit Distance SketchProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649783(956-967)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649783
Qi CLaili YRen LZhang LLi B(2024)A template augmented distant supervision framework for Chinese named entity recognitionInternational Journal of Modeling, Simulation, and Scientific Computing10.1142/S179396232450018115:01Online publication date: 19-Jan-2024
https://doi.org/10.1142/S1793962324500181
Bhattacharya SKoucký MSaha BServedio R(2023)Locally Consistent Decomposition of Strings with Applications to Edit Distance SketchingProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585239(219-232)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585239
Das DGilbert JHajiaghayi MKociumaka TSaha BSaha BServedio R(2023)Weighted Edit Distance Computation: Strings, Trees, and DyckProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585178(377-390)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585178
He XLi RSaha BServedio R(2023)Approximating Binary Longest Common Subsequence in Almost-Linear TimeProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585104(1145-1158)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585104
Cassis AKociumaka TWellnitz P(2023)Optimal Algorithms for Bounded Weighted Edit Distance2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00135(2177-2187)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00135
Kociumaka TMukherjee ASaha B(2023)Approximating Edit Distance in the Fully Dynamic Model2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00098(1628-1638)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00098
Bringmann KCohen-Addad VDas D(2022) A Linear-Time n 0.4 -Approximation for Longest Common Subsequence ACM Transactions on Algorithms10.1145/3568398Online publication date: 26-Oct-2022
https://doi.org/10.1145/3568398
Das DGilbert JHajiaghayi MKociumaka TSaha BSaleh H(2022)Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00071(686-697)Online publication date: Oct-2022
https://doi.org/10.1109/FOCS54457.2022.00071
Le Gall FSeddighin S(2022)Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String ProblemsAlgorithmica10.1007/s00453-022-01066-z85:5(1251-1286)Online publication date: 5-Dec-2022
https://doi.org/10.1007/s00453-022-01066-z
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents