Agenda

Speaker: Tomasz Kociumaka, Max Planck Institute for Informatics, Germany

Abstract:
I will cover selected recent results on the sublinear-time approximation of edit distance. This task is formalized as the (k,k^c)-Gap Edit Distance problem, where the input consists of a pair of strings X, Y and two parameters k, c > 1, and the goal is to return YES if ED(X, Y) <= k, NO if ED(X, Y) > k^c, and an arbitrary answer when k < ED(X, Y) <= k^c. I will first present a simple \tilde O(n/k^{c-1})-time algorithm that reduces the gap edit distance problem to an almost linear-time edit distance approximation. It is the first solution with sublinear runtime for the whole spectrum of parameters k, c > 1. Next, I will sketch how to obtain an improved non-adaptive algorithm with query complexity \tilde O(n/k^{c-0.5}), which is unconditionally optimal up to polylogarithmic factors. The algorithm also achieves optimal time complexity \tilde O(n/k^{c-0.5}) whenever c >= 1.5; for 1 < c < 1.5, the running time is \tilde O(n/k^{2c-1}).

Bio Sketch:
Tomasz Kociumaka is a postdoctoral researcher at the Max Planck Institute for Informatics, Germany. Tomasz received a Ph.D. from the University of Warsaw, Poland, in 2019, and then has been working at the Bar-Ilan University, Israel, and the University of California, Berkeley. His research revolves around designing efficient algorithms for processing strings (texts, sequences) with a particular focus on sequence similarity measures, approximate pattern matching, lossless data compression, and data structures. Tomasz studies string problems from multiple perspectives, including combinatorics on words, dynamic algorithms, fine-grained complexity, streaming and sketching, and sublinear algorithms.