Theory Seminar – Tomasz Kociumaka
Speaker: Tomasz Kociumaka, Max Planck Institute for Informatics, Germany
Logistics:
- Date: Wednesday, November 9, 2022
- In-person: Northwestern University Mudd Library 3514
- Time: 3:30 pm ( Chicago Time)
- Panopto: TBA
Title: Gap Edit Distance via Non-Adaptive Queries: Simple and Optimale
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 Ô(n/k^{c-1})-time algorithm that reduces the gap edit distance problem to 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 Õ(n/k^{c−0.5}), which is unconditionally optimal up to polylogarithmic factors. The algorithm also achieves optimal time complexity Õ(n/k^{c−0.5}) whenever c ≥ 1.5; for 1 < c < 1.5, the running time is Õ(n/k^{2c−1}).
Based on joint work with Elazar Goldenberg, Robert Krauthgamer, and Barna Saha, published at FOCS 2022. The full version is available at https://arxiv.org/abs/2111.12706.
Bio: I am a postdoctoral researcher at the Max Planck Institute for Informatics, Germany. I received a PhD from the University of Warsaw, Poland, in 2019, and then I have been working at the Bar-Ilan University, Israel, and the University of California, Berkeley. My 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. I study string problems from multiple perspectives, including combinatorics on words, dynamic algorithms, fine-grained complexity, streaming and sketching, and sublinear algorithms.