Abstract:A dimension reduction for hyperbolic space is established. When points are far apart, an embedding with bounded distortion into $H^2$ is achieved.
- Nir Ailon and Bernard Chazelle, Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform, STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, ACM, New York, 2006, pp. 557–563. MR 2277181, DOI 10.1145/1132516.1132597
- M. Bonk and O. Schramm, Embeddings of Gromov hyperbolic spaces, Geom. Funct. Anal. 10 (2000), no. 2, 266–306. MR 1771428, DOI 10.1007/s000390050009
- James W. Cannon, William J. Floyd, Richard Kenyon, and Walter R. Parry, Hyperbolic geometry, Flavors of geometry, Math. Sci. Res. Inst. Publ., vol. 31, Cambridge Univ. Press, Cambridge, 1997, pp. 59–115. MR 1491098
- William B. Johnson and Joram Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space, Conference in modern analysis and probability (New Haven, Conn., 1982) Contemp. Math., vol. 26, Amer. Math. Soc., Providence, RI, 1984, pp. 189–206. MR 737400, DOI 10.1090/conm/026/737400
- R. Krauthgamer and J. R. Lee, Algorithms on negatively curved spaces, Proc. of the 47th Symposium on Foundations of Computer Science, 2006, pp. 119–132.
- Jiří Matoušek, Bi-Lipschitz embeddings into low-dimensional Euclidean spaces, Comment. Math. Univ. Carolin. 31 (1990), no. 3, 589–600. MR 1078491
- Itai Benjamini
- Affiliation: Microsoft Research – and – Department of Mathematics, The Weizmann Institute, Rehovot 76100, Israel
- MR Author ID: 311800
- Email: firstname.lastname@example.org
- Yury Makarychev
- Affiliation: Microsoft Research New England, One Memorial Drive, Cambridge, Massachusetts 02142
- Email: email@example.com
- Received by editor(s): January 15, 2008
- Published electronically: September 12, 2008
- Communicated by: Mario Bonk
- © Copyright 2008
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
- Journal: Proc. Amer. Math. Soc. 137 (2009), 695-698
- MSC (2000): Primary 51M09, 68W40
- DOI: https://doi.org/10.1090/S0002-9939-08-09714-1
- MathSciNet review: 2448592