Barna Saha (UC San Diego)
[ Ссылка ]
Dynamic Graphs and Algorithm Design

Computing edit distance is a fundamental computer science problem where given two strings, the goal is to compute the minimum number of character substitutions, insertions, and deletions required to transform one string into the other. There are well-known dynamic programming algorithms from undergraduate textbooks that solve the edit distance problem in time quadratic in the string length which are also known to be optimal according to the Strong Exponential Time Hypothesis upto higher order terms. The last couple of decades have seen a tremendous research momentum in designing faster approximation algorithms for edit distance resulting in a myriad of wonderful results. However, the state of the art for computing edit distance in the dynamic setting where the strings can change over time was unsatisfactory. In this talk, I will cover our recent results in that area and discuss several open questions.

Joint work with Tomasz Kociumaka and Anish Mukherjee.

свернуть