AG 1   Info

AG Audience

English

120 Minutes

Saarbrücken

The edit distance between two strings is the minimum number of character insertions, deletions, and substitutions needed to transform one string into another. It is a fundamental string similarity measure with a variety of applications across several disciplines. The textbook algorithm computes edit distance in quadratic time, and there is little hope for significantly faster solutions due to conditional lower bounds. However, studying edit distance gives rise to numerous exciting questions that still await definite answers. In this tutorial, I will cover the basics of edit distance and introduce the seaweed method, originally due to Tiskin, as well as its applications for maintaining the edit distance of dynamic strings and computing the edit distance of compressed strings.

The lecture is primarily targeted at ADFOCS participants who were unable to attend the EPAC Workshop in May 2023, where I gave a 3-day tutorial "Modern Tools for Computing and Approximating Edit Distance".

Roohani Sharma

+49 681 9325 1116

--email hidden

Zoom

527 278 8807

passcode not visible

logged in users only

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