Conjugacy of finite subsets in hyperbolic groups

Martin R. Bridson, James Howie

Research output: Contribution to journalArticle

14 Citations (Scopus)

Abstract

There is a quadratic-time algorithm that determines conjugacy between finite subsets in any torsion-free hyperbolic group. Moreover, in any ?-generator, d-hyperbolic group G, if two finite subsets A and B are conjugate, then x-1 Ax = B for some x e G with ||x|| less than a linear function of max{||?|| : ? e A ? B}. (The coefficients of this linear function depend only on ? and d.) These results have implications for group-based cryptography and the geometry of homotopies in negatively curved spaces. In an appendix, we give examples of finitely presented groups in which the conjugacy problem for elements is soluble but the conjugacy problem for finite lists is not. © World Scientific Publishing Company.

Original languageEnglish
Pages (from-to)725-756
Number of pages32
JournalInternational Journal of Algebra and Computation
Volume15
Issue number4
DOIs
Publication statusPublished - Aug 2005

Keywords

  • Crytosystems
  • Decision problems
  • Hyperbolic groups
  • Short homotopies

Fingerprint Dive into the research topics of 'Conjugacy of finite subsets in hyperbolic groups'. Together they form a unique fingerprint.

Cite this