3 views

Skip to first unread message

May 12, 2023, 8:26:21 AM5/12/23

to BIU Theory Seminar, tomasz.k...@mpi-inf.mpg.de

Hello all,

Next week (Wed May 17, at 12) we will meet for our theory seminar.

While the theory community thoroughly studied the Levenshtein distance, most practical applications rely on a more general weighted edit distance, where each edit has a weight depending on its type and the involved characters from the alphabet Σ. This is formalized through a weight function w : Σ∪{ε} × Σ∪{ε} → ℝ normalized so that w(a,a) = 0 for a∊Σ∪{ε} and w(a,b) ≥ 1 for a,b∊Σ∪{ε} with a ≠ b. The classic O(n²)-time algorithm supports this setting seamlessly, but for many decades only a straightforward O(nk)-time solution was known for the bounded version of the weighted edit distance problem.

In this talk, I will present an O(n+k⁵)-time algorithm (joint work with Das, Gilbert, Hajiaghayi, and Saha; STOC'23; arXiv:2302.04229) and a very recent Õ(n+√{nk³})-time algorithm (joint work with Cassis and Wellnitz; arXiv:2305.06659). I will also sketch a lower bound that proves the optimality of the latter algorithm for √n ≤ k ≤ n (up to sub-polynomial factors and conditioned on the All-Pairs Shortest Paths Hypothesis).

May 17, 2023, 4:00:58 AM5/17/23

to BIU Theory Seminar, tomasz.k...@mpi-inf.mpg.de

The seminar starts in one hour, in the usual room (Building 605 room 14).

See you there!

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu