C C ] 2 O ct 2 01 9 Sublinear Algorithms for Gap Edit Distance ∗

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 nearlinear time [Andoni, Krauthgamer and Onak, FOCS 2010], and a constant-factor approximation in subquadratic time [Chakrabarty, Das, Goldenberg, Koucký 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 t2 (the quadratic gap problem) in time Õ( t + t 3). This time bound is sublinear roughly for all t in [ω(1), o(n1/3)], which was not known before. The best previous algorithms solve this problem in sublinear time only for t = ω(n1/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 t2−ǫ gap problem in time Õ( n t1−ǫ + t 3). Part of this work was done while the authors were visiting the Simons Institute for the Theory of Computing. The Academic College of Tel Aviv-Yaffo. Email: elazargo@mta.ac.il Weizmann Institute of Science. Work partially supported by ONR Award N00014-18-1-2364, the Israel Science Foundation grant #1086/18, and a Minerva Foundation grant. Email: robert.krauthgamer@weizmann.ac.il University of California Berkeley. Work partially supported by a NSF CAREER Award 1652303, and the Alfred P. Sloan Fellowship. Email: barnas@berkeley.edu