Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity

Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak

Type: Preprint

Publication Date: 2010-01-01

Citations: 2

DOI: https://doi.org/10.48550/arxiv.1005.4033

View Publication

Locations

arXiv (Cornell University) - View - PDF
CiteSeer X (The Pennsylvania State University) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity	2010	Alexandr Andoni Robert Krauthgamer Krzysztof Onak
+ PDF Chat	Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity	2010	Alexandr Andoni Robert Krauthgamer Krzysztof Onak
+	Asymmetric Streaming Algorithms for Edit Distance and LCS	2020	Alireza Farhadi MohammadTaghi Hajiaghayi Aviad Rubinstein Saeed Seddighin
+	Asymmetric Streaming Algorithms for Edit Distance and LCS	2020	Alireza Farhadi MohammadTaghi Hajiaghayi Aviad Rubinstein Saeed Seddighin
+	Edit Distance in Near-Linear Time: it's a Constant Factor	2020	Alexandr Andoni Negev Shekel Nosatzki
+	Space Efficient Deterministic Approximation of String Measures	2020	Kuan Cheng Zhengzhong Jin Xin Li Yu Zheng
+ PDF Chat	Approximating Edit Distance in Near-Linear Time	2012	Alexandr Andoni Krzysztof Onak
+	Edit Distance in Near-Linear Time: it's a Constant Factor	2020	Alexandr Andoni Negev Shekel Nosatzki
+	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 in near-linear time	2009	Alexandr Andoni Krzysztof Onak
+	Lower Bounds and Improved Algorithms for Asymmetric Streaming Edit Distance and Longest Common Subsequence	2021	Xin Li Yu Zheng
+	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
+	Approximate Similarity Search Under Edit Distance Using Locality-Sensitive Hashing	2019	Samuel McCauley
+	Small space and streaming pattern matching with k edits	2021	Tomasz Kociumaka Ely Porat Tatiana Starikovskaya
+	A Simple Sublinear Algorithm for Gap Edit Distance	2020	Joshua Brakensiek Moses Charikar Aviad Rubinstein
+	Small space and streaming pattern matching with k edits.	2021	Tomasz Kociumaka Ely Porat Tatiana Starikovskaya
+	Constant factor approximations to edit distance on far input pairs in nearly linear time	2019	Michal Koucký Michael Saks
+	Constant factor approximations to edit distance on far input pairs in nearly linear time	2019	Michal Koucký Michael Saks

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (0)

Action	Title	Year	Authors