Embedding the Ulam metric into ℓ1
by Moses Charikar and Robert Krauthgamer
Theory of Computing, Volume 2(11), pp. 207-224, 2006
Bibliography with links to cited articles
| [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:bull/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. [ .pdf ] |
| [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
Lp-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
L1.
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]. |
This file has been generated by bibtex2html 1.81.