22 citations · 34 across the 7 of their papers we have counts for
4 papers · 1 filter
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…
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 $…