Mahdi Safarnejad


Edit Distance and LCS: Beyond Worst Case

  Friday, 03 January 2020
  11:00 - 11:45


In the worst-case analysis of algorithms, the overall performance of an algorithm is summarized by its worst performance on any input. This approach has countless success stories. However, there are also major computational problems (like linear programming, clustering, and online caching) where the worst-case analysis framework does not provide any helpful advice on how to solve the problem.

In this talk, we study improved algorithms for edit distance and longest common subsequence, which are among the most fundamental problems in combinatorial optimization, beyond their worst-case. The proposed algorithms obtain $1+o(1)$ approximate solutions for both problems in truly subquadratic time if the input satisfies a mild condition. In this setting, first, an adversary chooses one of the input strings. Next, this string is perturbed by a random procedure. Then the adversary chooses the second string arbitrarily after observing the perturbed one.


Mahdi Safarnejad Boroujeni is a Ph.D. student at the Sharif University of Technology. He is supervised by Dr. Mohammad Ghodsi. His Research involves approximation algorithms for edit distance and similar problems. He also received his Bachelor and Master degrees from the Sharif University of Technology in Computer Engineering.