The Taub Faculty of Computer Science Events and Talks

(1) Edit distance oracles: preprocess two strings S and T of total length n into a data structure that can quickly report the optimal edit distance between any substring of S and any substring of T. I will describe a data structure with query time Õ(1), and construction time and space n^(2+o(1)). This is optimal up to subpolynomial factors since computing just the edit distance between S and T requires quadratic time (assuming the strong exponential time hypothesis). (2) Planar distance oracles: preprocess a directed weighted planar graph into a data structure that can quickly report the distance between any two vertices. Using the concept of Voronoi diagrams, dramatic progress has been made on planar distance oracles in the past few years. I will describe an oracle of almost linear n^{1+o(1)} size that answer queries in Õ(1) time. This is again optimal up to subpolynomial factors. However, the construction time is currently O(n^{1.5}), which is not known to be optimal. I will describe how ideas developed for planar distance oracles propagate to edit distance oracles. The structure of the edit distance graph allows for a simpler presentation of some of the techniques involved, and is further exploited to obtain a faster construction time. It is not uncommon that techniques originally developed for edit distance are later extended and generalized to planar graphs. Here, ideas propagate in the opposite direction; techniques originally developed for planar graphs are specialized to edit distance. Based on joint works with Panos Charalampopoulos, Pawel Gawrychowski and Shay Mozes (STOC 2019, ICALP 2021)