Conjugacy of Finite Subsets in Hyperbolic Groups.
There is a quadratic-time algorithm that determines conjugacy between finite subsets in any torsion-free hyperbolic group. Moreover, in any κ-generator, δ-hyperbolic group Γ, if two finite subsets A and B are conjugate, then x -1 Ax = B for some x ε Γ with ||x|| less than a...
| Үндсэн зохиолчид: | , |
|---|---|
| Формат: | Journal article |
| Хэл сонгох: | English |
| Хэвлэсэн: |
2005
|
| _version_ | 1826301452997361664 |
|---|---|
| author | Bridson, M Howie, J |
| author_facet | Bridson, M Howie, J |
| author_sort | Bridson, M |
| collection | OXFORD |
| description | There is a quadratic-time algorithm that determines conjugacy between finite subsets in any torsion-free hyperbolic group. Moreover, in any κ-generator, δ-hyperbolic group Γ, if two finite subsets A and B are conjugate, then x -1 Ax = B for some x ε Γ with ||x|| less than a linear function of max{||γ|| : γ ε A ∪ B}. (The coefficients of this linear function depend only on κ and δ.) 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. |
| first_indexed | 2024-03-07T05:32:39Z |
| format | Journal article |
| id | oxford-uuid:e2cdea59-7208-4949-b30b-e54c1fb54910 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T05:32:39Z |
| publishDate | 2005 |
| record_format | dspace |
| spelling | oxford-uuid:e2cdea59-7208-4949-b30b-e54c1fb549102022-03-27T10:04:07ZConjugacy of Finite Subsets in Hyperbolic Groups.Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:e2cdea59-7208-4949-b30b-e54c1fb54910EnglishSymplectic Elements at Oxford2005Bridson, MHowie, JThere is a quadratic-time algorithm that determines conjugacy between finite subsets in any torsion-free hyperbolic group. Moreover, in any κ-generator, δ-hyperbolic group Γ, if two finite subsets A and B are conjugate, then x -1 Ax = B for some x ε Γ with ||x|| less than a linear function of max{||γ|| : γ ε A ∪ B}. (The coefficients of this linear function depend only on κ and δ.) 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. |
| spellingShingle | Bridson, M Howie, J Conjugacy of Finite Subsets in Hyperbolic Groups. |
| title | Conjugacy of Finite Subsets in Hyperbolic Groups. |
| title_full | Conjugacy of Finite Subsets in Hyperbolic Groups. |
| title_fullStr | Conjugacy of Finite Subsets in Hyperbolic Groups. |
| title_full_unstemmed | Conjugacy of Finite Subsets in Hyperbolic Groups. |
| title_short | Conjugacy of Finite Subsets in Hyperbolic Groups. |
| title_sort | conjugacy of finite subsets in hyperbolic groups |
| work_keys_str_mv | AT bridsonm conjugacyoffinitesubsetsinhyperbolicgroups AT howiej conjugacyoffinitesubsetsinhyperbolicgroups |