Elazar Goldenberg

FOCS Conference 2022 Conference Paper

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

• Elazar Goldenberg
• Tomasz Kociumaka
• Robert Krauthgamer
• Barna Saha

We study the problem of approximating edit distance in sublinear time. This is formalized as the $(k, \ k^{\mathrm{c}})$-GAP EDIT DISTANCE problem, where the input is a pair of strings $X, \mathrm{Y}$ and parameters $k, c\gt 1$, and the goal is to return YES if ED(X, Y) $\leq k$, NO if ED(X, Y) $\gt k^{\mathrm{c}}$, and an arbitrary answer when $k\lt $ ED(X, Y) $\leq k^{\mathrm{c}}$. Recent years have witnessed significant interest in designing sublinear-time algorithms for GAP EDIT DISTANCE. In this work, we resolve the non-adaptive query complexity of GAP EDIT DISTANCE for the entire range of parameters, improving over a sequence of previous results. Specifically, we design a non-adaptive algorithm with query complexity $\tilde{O}(n/k^{\mathrm{c}-\mathrm{O}. 5})$, and we further prove that this bound is optimal up to polylogarithmic factors. Our algorithm also achieves optimal time complexity $\tilde{O}(n/k^{\mathrm{c}-\mathrm{O}. 5})$ whenever $ c\geq$ 1. 5. For $1 \lt c\lt $ 1. 5, the running time of our algorithm is $\tilde{O}(n/k^{2\mathrm{c}-2})$. In the restricted case of $k^{\mathrm{c}}=\Omega(n)$, this matches a known result [Batu, Ergün, Kilian, Magen, Raskhodnikova, Rubinfeld, and Sami; STOC 2003], and in all other (nontrivial) cases, our running time is strictly better than all previous algorithms, including the adaptive ones. However, independent work of Bringmann, Cassis, Fischer, and Nakos [STOC 2022] provides an adaptive algorithm that bypasses the non-adaptive lower bound, but only for small enough k and c.

STOC Conference 2020 Conference Paper

Does preprocessing help in fast sequence comparisons?

• Elazar Goldenberg
• Aviad Rubinstein
• Barna Saha

FOCS Conference 2019 Conference Paper

Sublinear Algorithms for Gap Edit Distance

• Elazar Goldenberg
• Robert Krauthgamer
• Barna Saha

The edit distance is a way of quantifying how similar two strings are to one another by counting the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. A simple dynamic programming computes the edit distance between two strings of length n in O(n2) time, and a more sophisticated algorithm runs in time O(n + t2) when the edit distance is t [Landau, Myers and Schmidt, SICOMP 1998]. In pursuit of obtaining faster running time, the last couple of decades have seen a flurry of research on approximating edit distance, including polylogarithmic approximation in near-linear time [Andoni, Krauthgamer and Onak, FOCS 2010], and a constant-factor approximation in subquadratic time [Chakrabarty, Das, Goldenberg, Kouck´y and Saks, FOCS 2018]. We study sublinear-time algorithms for small edit distance, which was investigated extensively because of its numerous applications. Our main result is an algorithm for distinguishing whether the edit distance is at most t or at least t^2 (the quadratic gap problem) in time Õ(n/t+t^3). This time bound is sublinear roughly for all t in [ω(1), o(n^1/3)], which was not known before. The best previous algorithms solve this problem in sublinear time only for t=ω(n^1/3) [Andoni and Onak, STOC 2009]. Our algorithm is based on a new approach that adaptively switches between uniform sampling and reading contiguous blocks of the input strings. In contrast, all previous algorithms choose which coordinates to query non-adaptively. Moreover, it can be extended to solve the t vs t^2-ε gap problem in time Õ(n/t^1-ε+t^3).

FOCS Conference 2018 Conference Paper

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

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

Edit distance is a measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a dynamic programming algorithm that runs in quadratic time. Andoni, Krauthgamer and Onak (2010) gave a nearly linear time algorithm that approximates edit distance within approximation factor poly(log n). In this paper, we provide an algorithm with running time Õ(n^2-2/7) that approximates the edit distance within a constant factor.

STOC Conference 2016 Conference Paper

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

• Diptarka Chakraborty
• Elazar Goldenberg
• Michal Koucký 0001

FOCS Conference 2008 Conference Paper

Locally Testing Direct Product in the Low Error Range

• Irit Dinur
• Elazar Goldenberg

Given a function f: X rarr Sigma, its lscr-wise direct product is the function F = f lscr: X lscr rarr Sigma lscr defined by: F(x 1, .. ., x lscr ) = (f(x 1 ), .. ., f(x lscr )). We are interested in the local testability of the direct product encoding (mapping f rarr f lscr ). Namely, given an arbitrary function F: X lscr rarr Sigma lscr, we wish to determine how close it is to f lscr for some f: X rarr Sigma, by making two random queries into F. In this work we analyze the case of low acceptance probability of the test. We show that even if the test passes with small probability, epsiv>0, already F must have a non-trivial structure and in particular must agree with some f lscr on nearly epsiv of the domain. Moreover, we give a structural characterization of all functions F on which the test passes with probability epsiv. Our results can be viewed as a combinatorial analog of the low error dasialow degree testpsila, that is used in PCP constructions.