ד"ר אלעזר גולדנברג

Strings Algorithms

אלגוריתמים

Can You Solve Closest String Faster than Exhaustive Search?
Amir Abboud, Nick Fischer, Elazar Goldenberg, Karthik C. S., Ron Safier, ESA 2023

An Algorithmic Bridge Between Hamming and Levenshtein Distances
Elazar Goldenberg, Tomasz Kociumaka , Robert Krauthgamer , and Barna Saha, ITCS 2023.

Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal
Elazar Goldenberg, Tomasz Kociumaka , Robert Krauthgamer , and Barna Saha, FOCS 2022.

Does Preprocessing help in Fast Sequence Comparisons?
Elazar Goldenberg, Aviad Rubinstein and Barna Saha,
STOC 2020.

Hardness Amplification of Optimization Problems
Karthik C.S., Elazar Goldenberg,
ITCS 2020.

Sublinear Algorithms for Gap Edit Distance
Elazar Goldenberg, Robert Krauthgamer and Barna Saha,
FOCS 2019.

Towards a General Direct Product Testing Theorem
Karthik C.S., Elazar Goldenberg,
FSTTCS 2018.

Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time,
Debarti Das, Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký and Michael Saks, FOCS 2018 (best paper award).

Local Reconstruction of Low-Rank Matrices and Subspaces
Roee David, Elazar Goldenberg and Robert Krauthgamer,
published in Random Structures & Algorithms.

Streaming algorithms for embedding and computing edit distance in the low distance regime
Diptarka Chakraborty, Elazar Goldenberg and Michal Koucký
STOC 2016.

Direct Sum Testing (see also the journal version).
Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, and Igor Shinkar
ITCS2015 and published in SICOMP.

Clustering in the Boolean Hypercube in a List Decoding Regime
Irit Dinur and Elazar Goldenberg
ICALP2013.

The Structure of Winning Strategies in Parallel Repetition Games
Irit Dinur and Elazar Goldenberg
RANDOM-APPROX 2010.

Locally Testing Direct Product in the High Error Range
Irit Dinur and Elazar Goldenberg
FOCS 2008.