Approximating Edit Distance
Halls department, Hall 3
Thursday, 29 December 2016
16:15 - 17:15
The edit distance of two strings is defined as the smallest number of insertions, deletions, and substitutions that need to be made to transform one of the strings to another one. Approximating edit distance in subquadratic time is one of the biggest unsolved problems in the field of combinatorial pattern matching. In this work, we give the first quantum constant approximation algorithm for computing the edit distance in truly subquadratic time. More precisely, we give an O(n1.857) quantum algorithm that approximates the edit distance within a factor of 7. We further extend this result to an O(n1.781) quantum algorithm that approximates the edit distance within a constant factor. This talk does not need any prior knowledge about quantum computing.
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.