AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

We present an algorithm which distinguishes whether the Edit Distance of two strings is at most k or at least k¹⁺ᵒ⁽¹⁾ in time O~(n/k + poly(k)). Our algorithm is almost optimal in the sense that for small k the running time becomes O(n/k), which matches a known n/k¹⁺ᵒ⁽¹⁾ lower bound (up to lower order factors).

Joint work with Karl Bringmann, Nick Fischer and Vasileios Nakos. The paper can be found in https://arxiv.org/abs/2202.08066 and will appear in STOC '22.

Roohani Sharma

+49 681 9325 1116

Zoom

527 278 8807

passcode not visible

logged in users only

The talk will take place in a hybrid format. In-person participants will meet in Room 024 at MPII and the virtual participants can join the mentioned zoom link. If you wish to join virtually and do not have the password for the zoom link, contact Roohani Sharma at rsharma@mpi-inf.mpg.de for the password.