%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% ToC#238 v002/a011.bib   Charikar - Krauthgamer
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

@inproceedings {BEKMRRS,
author = {T. Batu and F. Erg\"{u}n and J. Kilian and A. Magen and S.
Raskhodnikova and R. Rubinfeld and R. Sami},
title = {A sublinear algorithm for weakly approximating edit distance},
booktitle = {Proc. 35th STOC},
publisher = {ACM Press},
pages = {316--324},
year = {2003},
eprint="stoc:10.1145/780542.780590"
}

@article {Bourgain85,
  AUTHOR = {Bourgain, J.},
   TITLE = {On {L}ipschitz embedding of finite metric spaces in
{H}ilbert space},
 JOURNAL = {Israel J. Math.},
  VOLUME = {52},
    YEAR = {1985},
  NUMBER = {1-2},
   PAGES = {46--52},
}

@inproceedings{BJKK04,
  AUTHOR = {Z. Bar-Yossef and T. S. Jayram and R. Krauthgamer and R. Kumar},
   TITLE = {Approximating edit distance efficiently},
BOOKTITLE = {Proc. 45th FOCS},
   PAGES = {550--559},
PUBLISHER = {IEEE Computer Society Press},
    YEAR = {2004},
   eprint="focs:10.1109/FOCS.2004.14"
}

@inproceedings {CM02,
author = {G. Cormode and S. Muthukrishnan},
title = {The string edit distance matching problem with moves},
booktitle = {Proc. 13th Ann. ACM--SIAM Symp. on Discrete Algorithms (SODA'02)},
pages = {667--676},
year = {2002},
eprint="soda:545381.545470"
}

@phdthesis{Cormode:Thesis,
author={G. Cormode},
title={Sequence Distance Embeddings},
school={University of Warwick},
year={2003},
pdf="http://dimacs.rutgers.edu/~graham/pubs/cormode-seqdistembed.pdf"
}

@inproceedings{CMS01,
author={G. Cormode and S. Muthukrishnan and S. C. Sahinalp},
title={Permutation Editing and Matching via Embeddings},
booktitle = {Proc. 28th Internat. Coll. on Automata, Languages, and
Programming (ICALP'01)},
pages={481--492},
year={2001},
series={Lecture Notes in Computer Science},
volume={2076},
publisher={Springer},
eprint="icalp:hf0vwuh0rcyujug1"
}

@inproceedings {CPSV00,
author = {G. Cormode and M. Paterson and S. C. Sahinalp and U. Vishkin},
title = {Communication complexity of document exchange},
booktitle = {Proc. 11th Annual ACM--SIAM Symp. on Discrete Algorithms
(SODA'00)},
pages = {197--206},
year = {2000},
eprint="soda:338219.338252"
}

@incollection{FIMNSW,
  author = "J. Feigenbaum and Y. Ishai and T. Malkin and K. Nissim
and M. J. Strauss and R. N. Wright",
  title = "Secure Multiparty Computation of Approximations",
  booktitle = "Proceedings of 28th International Colloquium on
Automata, Languages, and Programming",
series = "Lecture Notes in Computer Science",
  volume = "2076",
  pages = "927--938",
  year = "2001",
publisher={Springer},
eprint="icalp:cpq5t97vrymq7q3n"
}

@inproceedings {IM98,
  AUTHOR = {Indyk, P. and Motwani, R.},
   TITLE = {Approximate nearest neighbors: towards removing the curse
of dimensionality},
BOOKTITLE = {30th STOC},
   PAGES = {604--613},
    YEAR = {1998},
publisher = {ACM Press},
eprint="stoc:10.1145/276698.276876"
}

@inproceedings{Indyk98,
author={P. Indyk},
title={On Approximate Nearest Neighbors in Non-Euclidean Spaces},
booktitle={Proc. 39th FOCS},
pages={148--155},
year={1998},
publisher={IEEE Computer Society Press},
eprint="focs:10.1109/SFCS.1998.743438"
}

@inproceedings{Indyk00,
author={P. Indyk},
title={Dimensionality reduction techniques for proximity problems},
booktitle={Proc. 11th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA'00)},
pages={371--378},
year={2000},
publisher={SIAM},
eprint="soda:338219.338582"
}

@inproceedings {Indyk04,
author = {P. Indyk},
title = {Approximate nearest neighbor under edit distance via product metrics},
booktitle = {Proc. 15th Ann. ACM--SIAM Symp. on Discrete Algorithms},
pages = {646--650},
year = {2004},
publisher={SIAM},
eprint="soda:982792.982889"
}

@article{KN05,
author={S. Khot and A. Naor},
title={Nonembeddability theorems via {F}ourier analysis},
journal={Mathematische Annalen},
volume=334,
number=4,
year=2006,
pages={821--852},
unused_doi={10.1007/s00208-005-0745-0},
unused_url={http://dx.doi.org/10.1007/s00208-005-0745-0},
eprint="springer:n4671147n1684344"
}

@inproceedings{KN05b,
author =       {S. Khot and A. Naor},
title =        {Nonembeddability theorems via {F}ourier {A}nalysis},
booktitle = {Proceedings of the 46th IEEE Symposium on Foundations of
Computer Science},
year =         {2005},
pages = {101--112},
eprint="focs:10.1109/SFCS.2005.54"
}

@ARTICLE{KOR00,
  AUTHOR = "E. Kushilevitz and R. Ostrovsky and Y. Rabani",
  TITLE = "Efficient Search for Approximate Nearest Neighbor in High
Dimensional Spaces",
  JOURNAL = "SIAM Journal on Computing",
  YEAR = 2000,
  VOLUME = 30,
  NUMBER = 2,
  PAGES = "457--474",
 eprint="sicomp:30/34717"
}

@inproceedings{KR06,
author={R. Krauthgamer and Y. Rabani},
title={Improved lower bounds for embeddings into {$L_1$}},
booktitle = {Proc. 16th Ann. ACM--SIAM Symp. on Discrete Algorithms},
year=2006,
pages={1010--1017},
publisher={SIAM},
eprint="soda:1109557.1109669"
}

@inproceedings{MS00,
author = {S. Muthukrishnan and S. C. Sahinalp},
title = {Approximate nearest neighbors and sequence comparisons with
block operations},
booktitle = {Proc. 32nd STOC},
pages = {416--424},
year = {2000},
publisher = {ACM Press},
eprint="stoc:10.1145/335305.335353"
}

@inproceedings {OR05,
author = {R. Ostrovsky and R. Rabani},
title = {Low Distortion Embeddings for Edit Distance},
booktitle = {Proc. 37th STOC},
pages={218--224},
year = {2005},
publisher = {ACM Press},
eprint="stoc:1060590.1060623"
}

@inproceedings {Yao79,
author = {A. C-C. Yao},
title = {Some complexity questions related to distributive computing},
pages = {209--213},
booktitle = {Proc. 11th STOC},
year = {1979},
publisher = {ACM Press},
eprint="stoc:10.1145/800135.804414"
}

@article {AD99,
  AUTHOR = {Aldous, D. and Diaconis, P.},
   TITLE = {Longest increasing subsequences: from patience sorting to
the {B}aik-{D}eift-{J}ohansson theorem},
 JOURNAL = {Bull. Amer. Math. Soc. (N.S.)},
FJOURNAL = {American Mathematical Society. Bulletin. New Series},
  VOLUME = {36},
    YEAR = {1999},
  NUMBER = {4},
   PAGES = {413--432},
    ISSN = {0273-0979},
  eprint = "bullams:bull/1999-36-04/S0273-0979-99-00796-X"
}

@article {Enflo69,
  AUTHOR = {Enflo, P.},
   TITLE = {On the nonexistence of uniform homeomorphisms between
${L}\sb{p}$-spaces},
 JOURNAL = {Ark. Mat.},
  VOLUME = {8},
    YEAR = {1969},
   PAGES = {103--105},
}

@inproceedings{GIM99,
author = {A. Gionis and P. Indyk and R. Motwani},
title = {Similarity Search in High Dimensions via Hashing},
booktitle = {Proc. 25th Internat. Conf. on Very Large Data Bases},
year = 1999,
publisher = {Morgan Kaufmann Publishers Inc.},
pages = {518--529},
eprint="vldb:645925.671516",
}