Conjugacy of finite subsets in hyperbolic groups

Martin R. Bridson, James Howie

Research output: Contribution to journalArticlepeer-review

21 Citations (Scopus)


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
Issue number4
Publication statusPublished - Aug 2005


  • Crytosystems
  • Decision problems
  • Hyperbolic groups
  • Short homotopies


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

Cite this