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

Michal Koucký, Michael Saks

Type: Preprint

Publication Date: 2019-04-10

Citations: 3

Locations

arXiv (Cornell University) - View

Similar Works

Action	Title	Year	Authors
+	Constant factor approximations to edit distance on far input pairs in nearly linear time	2019	Michal Koucký Michael Saks
+ PDF Chat	Constant factor approximations to edit distance on far input pairs in nearly linear time	2020	Michal Koucký Michael Saks
+	Edit Distance in Near-Linear Time: it's a Constant Factor	2020	Alexandr Andoni Negev Shekel Nosatzki
+	Constant-factor approximation of near-linear edit distance in near-linear time	2019	Joshua Brakensiek Aviad Rubinstein
+	Constant-factor approximation of near-linear edit distance in near-linear time	2019	Joshua Brakensiek Aviad Rubinstein
+ PDF Chat	Constant-factor approximation of near-linear edit distance in near-linear time	2020	Joshua Brakensiek Aviad Rubinstein
+	Edit Distance in Near-Linear Time: it's a Constant Factor	2020	Alexandr Andoni Negev Shekel Nosatzki
+ PDF Chat	Edit Distance in Near-Linear Time: it's a Constant Factor	2020	Alexandr Andoni Negev Shekel Nosatzki
+ PDF Chat	Approximating Edit Distance in Near-Linear Time	2012	Alexandr Andoni Krzysztof Onak
+ PDF Chat	Approximating edit distance in near-linear time	2009	Alexandr Andoni Krzysztof Onak
+	Sublinear Algorithms for Gap Edit Distance	2019	Elazar Goldenberg Robert Krauthgamer Barna Saha
+ PDF Chat	Faster Sublinear-Time Edit Distance	2024	Karl Bringmann Alejandro Cassis Nick Fischer Tomasz Kociumaka
+	Sublinear Algorithms for Gap Edit Distance	2019	Elazar Goldenberg Robert Krauthgamer Barna Saha
+ PDF Chat	Sublinear Algorithms for Gap Edit Distance	2019	Elazar Goldenberg Robert Krauthgamer Barna Saha
+	Approximating Edit Distance in Near-Linear Time	2011	Alexandr Andoni Krzysztof Onak
+	Approximating Edit Distance in Near-Linear Time	2011	Alexandr Andoni Krzysztof Onak
+ PDF Chat	Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time	2020	Diptarka Chakraborty Debarati Das Elazar Goldenberg Michal Koucký Michael Saks
+ PDF Chat	Almost Linear Size Edit Distance Sketch	2024	Michal Koucký Michael J. Saks
+ PDF Chat	Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time	2018	Diptarka Chakraborty Debarati Das Elazar Goldenberg Michal Koucký Michael Saks
+	Approximating the Geometric Edit Distance	2019	Kyle Fox Xinyi Li

Works That Cite This (3)

Action	Title	Year	Authors
+	Asymmetric Streaming Algorithms for Edit Distance and LCS	2020	Alireza Farhadi MohammadTaghi Hajiaghayi Aviad Rubinstein Saeed Seddighin
+	Constant-factor approximation of near-linear edit distance in near-linear time	2019	Joshua Brakensiek Aviad Rubinstein
+	Does Preprocessing help in Fast Sequence Comparisons	2021	Elazar Goldenberg Aviad Rubinstein Barna Saha

Works Cited by This (11)

Action	Title	Year	Authors
+	New tabulation and sparse dynamic programming based techniques for sequence similarity problems	2015	Szymon Grabowski
+ PDF Chat	Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping	2015	Karl Bringmann Marvin Künnemann
+ PDF Chat	Approximating edit distance in near-linear time	2009	Alexandr Andoni Krzysztof Onak
+ PDF Chat	Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity	2010	Alexandr Andoni Robert Krauthgamer Krzysztof Onak
+ PDF Chat	Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)	2015	Artūrs Bačkurs Piotr Indyk
+	Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made	2016	Amir Abboud Thomas Dueholm Hansen Virginia Vassilevska Williams Ryan Williams
+	Accurate and nearly optimal sublinear approximations to ulam distance	2017	Timothy Naumovitz Michael Saks C. Seshadhri
+	Approximate Online Pattern Matching in Sub-linear Time	2018	Diptarka Chakraborty Debarati Das Michal Koucký
+ PDF Chat	Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time	2018	Diptarka Chakraborty Debarati Das Elazar Goldenberg Michal Koucký Michael Saks
+ PDF Chat	Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce	2018	Mahdi Boroujeni Soheil Ehsani Mohammad Ghodsi MohammadTaghi Hajiaghayi Saeed Seddighin