Elazar Goldenberg

According to our database, Elazar Goldenberg authored at least 20 papers between 2008 and 2024.

Collaborative distances:

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

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

Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time.

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

J. ACM, 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

2019

Hardness Amplification of Optimization Problems.

Elazar Goldenberg, Karthik C. S.

Electron. Colloquium Comput. Complex., 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

2017

Direct Sum Testing.

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

SIAM J. Comput., 2017

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

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

Electron. Colloquium Comput. Complex., 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