Publications

• 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.