Bilkent University
Department of Computer Engineering


Testing Edit Distance in Sublinear Time

Funda Ergün

School of Computing Science,
Simon Fraser University,
Burnaby BC, Canada

The combinatorial property testing model has emerged as a relaxation of the exact computation model to be used in situations where the input is very large.  In this model, the goal is to compute, usually in sublinear time, whether the input has some predefined property or is far from satisfying it.

While the property to be thus tested can also be qualitative (eg. is graph G bipartite?), in this talk we will discuss a quantitative property, that of two sequences having a large edit distance.  We will present an algorithm which, given two sequences of length n, returns FAR if the edit distance between them is linear and CLOSE if it is at most n^k for some k<1.  The algorithm uses sampling and returns the correct answer with high probability over the choice of the samples, it runs in sublinear time in contrast with the quadratic running time of computing the edit distance exactly.  We also show a lower bound for the query complexity of an algorithm to solve this problem.

DATE: April 30, 2004, Friday @ 13:40