Nick Fischer, Weizmann Institute of Science

Abstract

We revisit the problem of approximating the edit distance of two strings. This important problem has been extensively studied in the last decades and has seen several breakthroughs in the literature, culminating in a constant-factor approximation in almost-linear time. However, why should we stop here---can we hope for similarly accurate approximation in *sublinear* time? In this talk I present an algorithm with subpolynomial (or even polylogarithmic) approximation factor in truly sublinear time O(n/k + poly(k)). This is *almost-optimal* in the regime where the edit distance k is comparably small (k < n^(1/3)). This result is based on joined work with Karl Bringmann, Alejandro Cassis, Tomasz Kociumaka, and Vasileios Nakos.

[Video]