22 citations · 34 across the 7 of their papers we have counts for
Showing 2019Show all
3 papers · 1 filter
cs.CC2019★ 1 cited
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…
cs.CC2019
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…
cs.CC2019
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 $…