22 citations · 34 across the 7 of their papers we have counts for
13 papers
Hardness of Median and Center in the Ulam Metric
Nick Fischer, Elazar Goldenberg, Mursalin Habib +1
The classical rank aggregation problem seeks to combine a set X of n permutations into a single representative "consensus" permutation. In this paper, we investigate two fundamenta…
Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric
Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg +4
A function is called an isometric embedding of the -dimensional Hamming metric space to the -dimensional edit metric space if, for all $x,y\in\{0,…
Many Flavors of Edit Distance
Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg +1
Several measures exist for string similarity, including notable ones like the edit distance and the indel distance. The former measures the count of insertions, deletions, and subs…
Explicit Good Codes Approaching Distance 1 in Ulam Metric
Elazar Goldenberg, Mursalin Habib, Karthik C. S
The Ulam distance of two permutations on is minus the length of their longest common subsequence. In this paper, we show that for every , there exists some…
Can You Solve Closest String Faster than Exhaustive Search?
Amir Abboud, Nick Fischer, Elazar Goldenberg +2
We study the fundamental problem of finding the best string to represent a given set, in the form of the Closest String problem: Given a set of strings, find…
An Algorithmic Bridge Between Hamming and Levenshtein Distances
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer +1
The edit distance between strings classically assigns unit cost to every character insertion, deletion, and substitution, whereas the Hamming distance only allows substitutions. In…
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 -Gap Edit Distance problem, where the input is a pair of strings and…
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…