Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity.

Alexandr Andoni Robert Krauthgamer Krzysztof Onak

Published in: FOCS (2010)

Keyphrases

edit distance
query complexity
similarity measure
membership queries
edit operations
graph matching
data complexity
distance measure
distance function
exact learning
dynamic programming
concept class
approximation algorithms
databases
object recognition
point sets