[1]   D. Aldous and P. Diaconis: Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bull. Amer. Math. Soc. (N.S.), 36(4):413–432, 1999. [BullAMS:1999-36-04/S0273-0979-99-00796-X].

[2]   Z. Bar-Yossef, T. S. Jayram, R. Krauthgamer, and R. Kumar: Approximating edit distance efficiently. In Proc. 45th FOCS, pp. 550–559. IEEE Computer Society Press, 2004. [FOCS:10.1109/FOCS.2004.14].

[3]   T. Batu, F. Ergün, J. Kilian, A. Magen, S. Raskhodnikova, R. Rubinfeld, and R. Sami: A sublinear algorithm for weakly approximating edit distance. In Proc. 35th STOC, pp. 316–324. ACM Press, 2003. [STOC:10.1145/780542.780590].

[4]   J. Bourgain: On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math., 52(1-2):46–52, 1985.

[5]   G. Cormode: Sequence Distance Embeddings. PhD thesis, University of Warwick, 2003.

[6]   G. Cormode and S. Muthukrishnan: The string edit distance matching problem with moves. In Proc. 13th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’02), pp. 667–676, 2002. [SODA:545381.545470].

[7]   G. Cormode, S. Muthukrishnan, and S. C. Sahinalp: Permutation editing and matching via embeddings. In Proc. 28th Internat. Coll. on Automata, Languages, and Programming (ICALP’01), volume 2076 of Lecture Notes in Computer Science, pp. 481–492. Springer, 2001. [ICALP:hf0vwuh0rcyujug1].

[8]   G. Cormode, M. Paterson, S. C. Sahinalp, and U. Vishkin: Communication complexity of document exchange. In Proc. 11th Annual ACM–SIAM Symp. on Discrete Algorithms (SODA’00), pp. 197–206, 2000. [SODA:338219.338252].

[9]   P. Enflo: On the nonexistence of uniform homeomorphisms between L_p-spaces. Ark. Mat., 8:103–105, 1969.

[10]   J. Feigenbaum, Y. Ishai, T. Malkin, K. Nissim, M. J. Strauss, and R. N. Wright: Secure multiparty computation of approximations. In Proceedings of 28th International Colloquium on Automata, Languages, and Programming, volume 2076 of Lecture Notes in Computer Science, pp. 927–938. Springer, 2001. [ICALP:cpq5t97vrymq7q3n].

[11]   A. Gionis, P. Indyk, and R. Motwani: Similarity search in high dimensions via hashing. In Proc. 25th Internat. Conf. on Very Large Data Bases, pp. 518–529. Morgan Kaufmann Publishers Inc., 1999. [VLDB:645925.671516].

[12]   P. Indyk: On approximate nearest neighbors in non-euclidean spaces. In Proc. 39th FOCS, pp. 148–155. IEEE Computer Society Press, 1998. [FOCS:10.1109/SFCS.1998.743438].

[13]   P. Indyk: Dimensionality reduction techniques for proximity problems. In Proc. 11th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’00), pp. 371–378. SIAM, 2000. [SODA:338219.338582].

[14]   P. Indyk: Approximate nearest neighbor under edit distance via product metrics. In Proc. 15th Ann. ACM–SIAM Symp. on Discrete Algorithms, pp. 646–650. SIAM, 2004. [SODA:982792.982889].

[15]   P. Indyk and R. Motwani: Approximate nearest neighbors: towards removing the curse of dimensionality. In 30th STOC, pp. 604–613. ACM Press, 1998. [STOC:10.1145/276698.276876].

[16]   S. Khot and A. Naor: Nonembeddability theorems via Fourier analysis. Mathematische Annalen, 334(4):821–852, 2006. [Springer:n4671147n1684344].

[17]   R. Krauthgamer and Y. Rabani: Improved lower bounds for embeddings into L₁. In Proc. 16th Ann. ACM–SIAM Symp. on Discrete Algorithms, pp. 1010–1017. SIAM, 2006. [SODA:1109557.1109669].

[18]   E. Kushilevitz, R. Ostrovsky, and Y. Rabani: Efficient search for approximate nearest neighbor in high dimensional spaces. SIAM Journal on Computing, 30(2):457–474, 2000. [SICOMP:30/34717].

[19]   S. Muthukrishnan and S. C. Sahinalp: Approximate nearest neighbors and sequence comparisons with block operations. In Proc. 32nd STOC, pp. 416–424. ACM Press, 2000. [STOC:10.1145/335305.335353].

[20]   R. Ostrovsky and R. Rabani: Low distortion embeddings for edit distance. In Proc. 37th STOC, pp. 218–224. ACM Press, 2005. [STOC:1060590.1060623].

[21]   A. C-C. Yao: Some complexity questions related to distributive computing. In Proc. 11th STOC, pp. 209–213. ACM Press, 1979. [STOC:10.1145/800135.804414].