Almost Linear Size Edit Distance Sketch

Edit distance is an important measure of string similarity. It counts the number of insertions, deletions and substitutions one has to make to a string x to get a string y. In this paper we design an almost linear-size sketching scheme for computing edit distance up to a given threshold k. The scheme consists of two algorithms, a sketching algorithm and a recovery algorithm. The sketching algorithm depends on the parameter k and takes as input a string x and a public random string ρ and computes a sketch sk ρ (x; k), which is a digested version of x. The recovery algorithm is given two sketches sk ρ (x; k) and sk ρ (y; k) as well as the public random string ρ used to create the two sketches, and (with high probability) if the edit distance ED(x, y) between x and y is at most k, will output ED(x, y) together with an optimal sequence of edit operations that transforms x to y, and if ED(x, y) > k will output large. The size of the sketch output by the sketching algorithm on input

(where n is an upper bound on length of x). The sketching and recovery algorithms both run in time polynomial in n. The dependence of sketch size on k is information theoretically optimal and improves over the quadratic dependence on k in schemes of Kociumaka, Porat and Starikovskaya (FOCS'2021), andBhattacharya and Koucký (STOC'2023).