Many Flavors of Edit Distance
Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg, Michal Koucký
FSTTCS 2024
Explicit Good Codes Approaching Distance 1 in Ulam Metric
Elazar Goldenberg, Mursalin Habib Karthik C. S.,
ISIT 2024
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, slides.
Towards a General Direct Product Testing Theorem
Karthik C.S., Elazar Goldenberg,
Published in FSTTCS 2018, check here for the journal version published in TOCT.
Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time, (slides)
Debarti Das, Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký and Michael Saks,
FOCS 2018 (best paper award).
Streaming Algorithms For Computing Edit Distance Without Exploiting Suffix Trees
Diptarka Chakraborty, Elazar Goldenberg and Michal Koucký,
submitted.
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.