Elazar Goldenberg

According to our database, Elazar Goldenberg authored at least 22 papers between 2008 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of two.

2025

Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric.

Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg, Mursalin Habib, Bernhard Haeupler, Karthik C. S., Michal Koucký

CoRR, April, 2025

Hardness of Median and Center in the Ulam Metric.

Nick Fischer, Elazar Goldenberg, Mursalin Habib, Karthik C. S.

Proceedings of the 33rd Annual European Symposium on Algorithms, 2025

2024

Explicit Good Codes Approaching Distance 1 in Ulam Metric.

Elazar Goldenberg, Mursalin Habib, Karthik C. S.

Proceedings of the IEEE International Symposium on Information Theory, 2024

Many Flavors of Edit Distance.

Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg, Michal Koucký

Proceedings of the 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2024

2023

An Algorithmic Bridge Between Hamming and Levenshtein Distances.

Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Can You Solve Closest String Faster Than Exhaustive Search?

Amir Abboud, Nick Fischer, Elazar Goldenberg, Karthik C. S., Ron Safier

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal.

Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2020

Toward a General Direct Product Testing Theorem.

Elazar Goldenberg, Karthik C. S.

ACM Trans. Comput. Theory, 2020

Does preprocessing help in fast sequence comparisons?

Elazar Goldenberg, Aviad Rubinstein, Barna Saha

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Hardness Amplification of Optimization Problems.

Elazar Goldenberg, Karthik C. S.

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019

Sublinear Algorithms for Gap Edit Distance.

Elazar Goldenberg, Robert Krauthgamer, Barna Saha

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Towards a General Direct Product Testing Theorem.

Elazar Goldenberg, Karthik C. S.

Proceedings of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2018

Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time.

Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2016

Streaming Algorithms For Computing Edit Distance Without Exploiting Suffix Trees.

Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký

CoRR, 2016

Streaming algorithms for embedding and computing edit distance in the low distance regime.

Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015

Local Reconstruction of Low-Rank Matrices and Subspaces.

Roee David, Elazar Goldenberg, Robert Krauthgamer

Electron. Colloquium Comput. Complex., 2015

Low Distortion Embedding from Edit to Hamming Distance using Coupling.

Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký

Electron. Colloquium Comput. Complex., 2015

Direct Sum Testing.

Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

2014

Information Complexity for Multiparty Communication.

Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký

Electron. Colloquium Comput. Complex., 2014

2013

Clustering in the Boolean Hypercube in a List Decoding Regime.

Irit Dinur, Elazar Goldenberg

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2010

The Structure of Winning Strategies in Parallel Repetition Games.

Irit Dinur, Elazar Goldenberg

Proceedings of the Approximation, 2010

2008

Locally Testing Direct Product in the Low Error Range.

Irit Dinur, Elazar Goldenberg

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008