Bilkent University
Department of Computer Engineering
S E M I N A R
Testing
Edit Distance in Sublinear Time
Funda Ergün
School of Computing Science,
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
PLACE: EA-502