Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Dimension reduction for hyperbolic space

Authors: Itai Benjamini and Yury Makarychev
Journal: Proc. Amer. Math. Soc. 137 (2009), 695-698
MSC (2000): Primary 51M09, 68W40
Published electronically: September 12, 2008
MathSciNet review: 2448592
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A dimension reduction for hyperbolic space is established. When points are far apart, an embedding with bounded distortion into $ H^2$ is achieved.

References [Enhancements On Off] (What's this?)

  • 1. N. Ailon and B. Chazelle,
    Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform,
    Proc. of the 38th Annual ACM Symposium on Theory of Computing, ACM, New York, 2006, pp. 557-563. MR 2277181 (2007h:68074)
  • 2. M. Bonk and O. Schramm,
    Embeddings of Gromov hyperbolic spaces,
    Geom. Funct. Anal. 10 (2000), no. 2, 266-306. MR 1771428 (2001g:53077)
  • 3. J. Cannon, W. Floyd, R. Kenyon, and W. Parry,
    Hyperbolic geometry,
    Flavors of Geometry, Math. Sci. Res. Inst. Publ., 31, Cambridge Univ. Press, Cambridge, 1997, pp. 59-115. MR 1491098 (99c:57036)
  • 4. W. B. Johnson and J. Lindenstrauss,
    Extensions of Lipschitz mappings into a Hilbert space,
    Contemp. Math., 26, Amer. Math. Soc., Providence, RI (1984), 189-206. MR 0737400 (86a:46018)
  • 5. 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.
  • 6. J. Matoušek.
    Bi-Lipschitz embeddings into low-dimensional Euclidean spaces,
    Comment. Math. Univ. Carolin. 31 (1990), no. 3, 589-600. MR 1078491 (91k:54056)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 51M09, 68W40

Retrieve articles in all journals with MSC (2000): 51M09, 68W40

Additional Information

Itai Benjamini
Affiliation: Microsoft Research – and – Department of Mathematics, The Weizmann Institute, Rehovot 76100, Israel

Yury Makarychev
Affiliation: Microsoft Research New England, One Memorial Drive, Cambridge, Massachusetts 02142

Received by editor(s): January 15, 2008
Published electronically: September 12, 2008
Communicated by: Mario Bonk
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society