Tugkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, Rahul Sami
A sublinear algorithm for weakly approximating edit distance
STOC, 2003.
@inproceedings{STOC-2003-BatuEKMRRS,
author = "Tugkan Batu and Funda Ergün and Joe Kilian and Avner Magen and Sofya Raskhodnikova and Ronitt Rubinfeld and Rahul Sami",
booktitle = "{Proceedings of the 35th Annual ACM Symposium on Theory of Computing}",
doi = "10.1145/780542.780590",
isbn = "1-58113-674-9",
pages = "316--324",
publisher = "{ACM}",
title = "{A sublinear algorithm for weakly approximating edit distance}",
year = 2003,
}