9 citations · 10 across the 3 of their papers we have counts for
6 papers
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…
Sublinear Algorithms for Gap Edit Distance
Elazar Goldenberg, Robert Krauthgamer, Barna Saha
The edit distance is a way of quantifying how similar two strings are to one another by counting the minimum number of character insertions, deletions, and substitutions required t…
Hardness Amplification of Optimization Problems
Elazar Goldenberg, Karthik C. S.
In this paper, we prove a general hardness amplification scheme for optimization problems based on the technique of direct products. We say that an optimization problem is dire…
Towards a General Direct Product Testing Theorem
Elazar Goldenberg, Karthik C. S.
The Direct Product encoding of a string on an underlying domain , is a function DP which gets as input a set and outputs $…
Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time
Diptarka Chakraborty, Debarati Das, Elazar Goldenberg +2
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…
Streaming Algorithms For Computing Edit Distance Without Exploiting Suffix Trees
Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký
The edit distance is a way of quantifying how similar two strings are to one another by counting the minimum number of character insertions, deletions, and substitutions required t…