Elazar Goldenberg

List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

Publication	Date of Publication	Type
Hardness of median and center in the Ulam metric	2026-08-31	Paper
Many flavors of edit distance	2026-06-12	Paper
Gap edit distance via non-adaptive queries: simple and optimal	2025-08-15	Paper
Approximating edit distance within constant factor in truly sub-quadratic time	2025-08-12	Paper
Sublinear algorithms for gap edit distance	2025-08-12	Paper
Explicit good codes approaching distance 1 in Ulam metric IEEE Transactions on Information Theory	2025-07-14	Paper
Can you solve closest string faster than exhaustive search?	2025-01-06	Paper
An algorithmic bridge between Hamming and Levenshtein distances	2024-09-25	Paper
Hardness Amplification of Optimization Problems (available as arXiv preprint)	2023-02-03	Paper
Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time Journal of the ACM	2022-12-08	Paper
Toward a general direct product testing theorem ACM Transactions on Computation Theory	2022-12-05	Paper
Towards a general direct product testing theorem (available as arXiv preprint)	2022-07-21	Paper
Does preprocessing help in fast sequence comparisons? Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing	2021-01-19	Paper
Local reconstruction of low-rank matrices and subspaces Random Structures & Algorithms	2017-12-13	Paper
Streaming algorithms for embedding and computing edit distance in the low distance regime Proceedings of the forty-eighth annual ACM symposium on Theory of Computing	2017-09-29	Paper
Direct sum testing SIAM Journal on Computing	2017-08-16	Paper
Direct sum testing (extended abstract) Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science	2017-05-19	Paper
Clustering in the Boolean hypercube in a list decoding regime Automata, Languages, and Programming	2013-08-06	Paper
The structure of winning strategies in parallel repetition games Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques	2010-09-10	Paper
Explicit Good Codes Approaching Distance 1 in Ulam Metric (available as arXiv preprint)	N/A	Paper

Research outcomes over time

This page was built for person: Elazar Goldenberg