Dr. Goldenberg Elazar
Fields of Research
School of Computer Science
Algorithms design
Fine-grained complexity
Edit Distance computation.
Short Bio
Dr. Elazar is a lecturer and a researcher at the Academic College of Tel Aviv-Yaffo. He has dedicated
his academic career to the study of various theoretical aspects of computer science; mainly in the
subjects of fine-grained complexity, sublinear and on-line algorithms, and property testing.
Selected Publications
1. Does Preprocessing help in Fast Sequence Comparisons?, Elazar Goldenberg, Aviad Rubinstein and Barna Saha, STOC 2020 .
2. Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal. Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, and Barna Saha. FOCS 2022.
3. Sublinear Algorithms for Gap Edit Distance, Elazar Goldenberg, Robert Krauthgamer and Barna Saha, FOCS 2019.
4. Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time, Debarti Das, Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký and Michael Saks, FOCS 2018, Best Paper Award.
5. Streaming algorithms for embedding and computing edit distance in the low distance regime, Diptarka Chakraborty, Elazar Goldenberg and Michal Koucký, STOC 2016.
6. Locally Testing Direct Product in the Low Error Range, Irit Dinur and Elazar Goldenberg, FOCS 2008.