MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal

Tomasz Kociumaka
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience
English

Date, Time and Location

Thursday, 27 October 2022
13:00
30 Minutes
E1 4
024
Saarbrücken

Abstract

We study the problem of approximating edit distance in sublinear time. This is formalized as the (k,k^c)-Gap Edit Distance problem, where the input is a pair of strings X, Y and 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. Recent years have witnessed significant interest in designing sublinear-time algorithms for Gap Edit Distance.


In this work, we resolve the non-adaptive query complexity of Gap Edit Distance for the entire range of parameters, improving over a sequence of previous results. Specifically, we design a non-adaptive algorithm with query complexity Õ(n/k^{c−0.5}), and we further prove that this bound is optimal up to polylogarithmic factors.

Our algorithm also achieves optimal time complexity Õ(n/k^{c−0.5}) whenever c ≥ 1.5. For 1 < c < 1.5, the running time of our algorithm is Õ(n/k^{2c−1}). In the restricted case of k^c = Ω(n), this matches a known result [Batu, Ergün, Kilian, Magen, Raskhodnikova, Rubinfeld, and Sami; STOC 2003], and in all other (nontrivial) cases, our running time is strictly better than all previous algorithms, including the adaptive ones. However, an independent work of Bringmann, Cassis, Fischer, and Nakos [STOC 2022] provides an adaptive algorithm that bypasses the non-adaptive lower bound, but only for small k and c.

This is joint work with Elazar Goldenberg, Robert Krauthgamer, and Barna Saha. To be presented at FOCS 2022, with the full version available at https://arxiv.org/abs/2111.12706v2.

Contact

Roohani Sharma
+49 681 9325 1116
Zoom
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

If you wish to attend the talk online but does not have the zoom password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.

Roohani Sharma, 10/10/2022 18:24
Roohani Sharma, 10/05/2022 10:56
Roohani Sharma, 10/04/2022 16:53 -- Created document.