Elazar Goldenberg

Publication Activity (10 Years)

Years Active: 2008-2024
Publications (10 Years): 24

Top Topics

Exhaustive Search

Constant Factor

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Elazar Goldenberg, Mursalin Habib, Karthik C. S.
Explicit Good Codes Approaching Distance 1 in Ulam Metric. CoRR (2024)
Amir Abboud, Nick Fischer, Elazar Goldenberg, Karthik C. S., Ron Safier
Can You Solve Closest String Faster Than Exhaustive Search? ESA (2023)
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha
An Algorithmic Bridge Between Hamming and Levenshtein Distances. ITCS (2023)
Amir Abboud, Nick Fischer, Elazar Goldenberg, Karthik C. S., Ron Safier
Can You Solve Closest String Faster than Exhaustive Search? CoRR (2023)
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha
An Algorithmic Bridge Between Hamming and Levenshtein Distances. CoRR (2022)
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal. FOCS (2022)
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal. CoRR (2021)
Elazar Goldenberg, Aviad Rubinstein, Barna Saha
Does Preprocessing help in Fast Sequence Comparisons? CoRR (2021)
Elazar Goldenberg, Aviad Rubinstein, Barna Saha
Does preprocessing help in fast sequence comparisons? STOC (2020)
Elazar Goldenberg, Karthik C. S.
Toward a General Direct Product Testing Theorem. ACM Trans. Comput. Theory 12 (1) (2020)
Elazar Goldenberg, Karthik C. S.
Hardness Amplification of Optimization Problems. ITCS (2020)
Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks
Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time. J. ACM 67 (6) (2020)
Elazar Goldenberg, Robert Krauthgamer, Barna Saha
Sublinear Algorithms for Gap Edit Distance. FOCS (2019)
Elazar Goldenberg, Karthik C. S.
Hardness Amplification of Optimization Problems. Electron. Colloquium Comput. Complex. 26 (2019)
Elazar Goldenberg, Karthik C. S.
Towards a General Direct Product Testing Theorem. CoRR (2019)
Elazar Goldenberg, Robert Krauthgamer, Barna Saha
Sublinear Algorithms for Gap Edit Distance. CoRR (2019)
Elazar Goldenberg, Karthik C. S.
Hardness Amplification of Optimization Problems. CoRR (2019)
Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks
Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time. FOCS (2018)
Elazar Goldenberg, Karthik C. S.
Towards a General Direct Product Testing Theorem. FSTTCS (2018)
Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks
Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time. CoRR (2018)
Roee David, Elazar Goldenberg, Robert Krauthgamer
Local reconstruction of low-rank matrices and subspaces. Random Struct. Algorithms 51 (4) (2017)
Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar
Direct Sum Testing. SIAM J. Comput. 46 (4) (2017)
Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký
Streaming algorithms for embedding and computing edit distance in the low distance regime. STOC (2016)
Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký
Streaming Algorithms For Computing Edit Distance Without Exploiting Suffix Trees. CoRR (2016)
Roee David, Elazar Goldenberg, Robert Krauthgamer
Local Reconstruction of Low-Rank Matrices and Subspaces. Electron. Colloquium Comput. Complex. 22 (2015)
Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar
Direct Sum Testing. ITCS (2015)
Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký
Low Distortion Embedding from Edit to Hamming Distance using Coupling. Electron. Colloquium Comput. Complex. 22 (2015)
Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký
Information Complexity for Multiparty Communication. Electron. Colloquium Comput. Complex. 21 (2014)
Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar
Direct Sum Testing. Electron. Colloquium Comput. Complex. 21 (2014)
Irit Dinur, Elazar Goldenberg
Clustering in the Boolean Hypercube in a List Decoding Regime. Electron. Colloquium Comput. Complex. 20 (2013)
Irit Dinur, Elazar Goldenberg
Clustering in the Boolean Hypercube in a List Decoding Regime. ICALP (1) (2013)
Irit Dinur, Elazar Goldenberg
The Structure of Winning Strategies in Parallel Repetition Games. APPROX-RANDOM (2010)
Irit Dinur, Elazar Goldenberg
Locally Testing Direct Product in the Low Error Range. FOCS (2008)