Elazar Goldenberg

activity

20162025

most citedApproximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time

22 citations · 34 across the 7 of their papers we have counts for

collaborators

Showing 2021Show all

2 papers · 1 filter

cs.DS2021

Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal

Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer +1

We study the problem of approximating edit distance in sublinear time. This is formalized as the $(k, k^{c})$ -Gap Edit Distance problem, where the input is a pair of strings $X, Y$ and…

cs.DS2021

Does Preprocessing help in Fast Sequence Comparisons?

Elazar Goldenberg, Aviad Rubinstein, Barna Saha

We study edit distance computation with preprocessing: the preprocessing algorithm acts on each string separately, and then the query algorithm takes as input the two preprocessed…