The conjugacy length function of a group Γ determines, for a given a pair of conjugate elements u,v ∈ Γ, an upper bound for the shortest γ in Γ such that uγ = γv, relative to the lengths of u and v. This thesis focuses on estimating the conjugacy length function in certain finitely generated groups. We first look at a collection of solvable groups. We see how the lamplighter groups have a linear conjugacy length function; we find a cubic upper bound for free solvable groups; for solvable Baumslag--Solitar groups it is linear, while for a larger family of abelian-by-cyclic groups we get either a linear or exponential upper bound; also we show that for certain polycyclic metabelian groups it is at most exponential. We also investigate how taking a wreath product effects conjugacy length, as well as other group extensions. The Magnus embedding is an important tool in the study of free solvable groups. It embeds a free solvable group into a wreath product of a free abelian group and a free solvable group of shorter derived length. Within this thesis we show that the Magnus embedding is a quasi-isometric embedding. This result is not only used for obtaining an upper bound on the conjugacy length function of free solvable groups, but also for giving a lower bound for their L_p compression exponents. Conjugacy length is also studied between certain types of elements in lattices of higher-rank semisimple real Lie groups. In particular we obtain linear upper bounds for the length of a conjugator from the ambient Lie group within certain families of real hyperbolic elements and unipotent elements. For the former we use the geometry of the associated symmetric space, while for the latter algebraic techniques are employed.

Dans la thèse présente, nous nous intéressons à l'étude de la relative hyperbolicité des produits semi-direct des produits libres, ainsi que le problème de conjugaison pour certains automorphismes de ces produits libres.Plus précisement, pour un produit libre $$G=G_1astdotsast G_past F_k$$ un automorphisme $phi$ est intitulé atoroidal s'il ne fixe pas (ni aucune de ses puissances) la classe de conjugaison d'un élément hyperbolique de $G$. Cet automorphisme est appelé completement irréductible si le système de facteurs libres est le plus grand qui est fixé par toutes les puissances de cet automorphisme. Il est appelé toral si pour tous les $i$, il existe $g_iin G$ tel que ${rm ad}_{g_i}circ phi|_{G_i}$ est identité sur le facteur libre $G_i$. Nous disons qu'il a la condition centrale si pour chaque $i$, il existe $g_iin G$ conjugue $phi(G_i)$ à $G_i$, et s'il existe un élément non trivial de $G_irtimes_{{rm ad}_{g_i} circ phi|_{G_i}} mathbb{Z}$ qui est central dans $G_irtimes_{{rm ad}_{g_i} circ phi|_{G_i}} mathbb{Z}$.Nous prouvons, dans le Théorème 4.28, que si $phi$ est atoroidal et completement irréductible, et si le produit libre est non-elementaire ($kgeq 2$ ou $ p+k geq 3$), le groupe $Grtimes_phi mathbb{Z}$ est relativement hyperbolique (relativement a des suspensions de chaque $G_i$). Après, dans le Théorème 6.10, nous prouvons le même résultat si $phi$ est atoroidal avec la condition centrale. Nous prouvons aussi dans le Théorème 7.21 que si tous les $G_i$ sont abelien, le problème de conjugaison est solvable pour les automorphismes atoroidaux, toraux. Ces sont des analogues du résultat de Brinkmann [7] (celui qui a donné le résultat d'hyperbolicité pour les groupes libres), et du résultat de Dahmani [12] (celui qui a résolu le problème de conjugaison des automorphismes hyperboliques). / In this thesis, we are interested in the study of the relative hyperbolicity of the suspensions of free products, as well as the conjugacy problem of certain automorphisms of free products.To be more precise, given a free product $$G=G_1astdotsast G_past F_k$$ an automorphism $phi$ is said atoroidal if no power fixes the conjugacy class of an hyperbolic element. It is called fully irreducible if the given free factor system $[G_1],dots,[G_p]$ is the largest one that is fixed by every power of the automorphism. It is said toral if for all $i$, there exists $g_iin G$ such that ${rm ad}_{g_i}circ phi|_{G_i}$ is the identity on the free factor $G_i$. It is said to have central condition if for each $i$, there exists $g_iin G$ conjugating $phi(G_i)$ to $G_i$, and if there exists a non-trivial element of $G_irtimes_{{rm ad}_{g_i} circ phi|_{G_i}} mathbb{Z}$ that is central in $G_irtimes_{{rm ad}_{g_i} circ phi|_{G_i}} mathbb{Z}$.We prove, in Theorem 4.28, that if $phi$ is atoroidal and fully irreducible, and if the free product is non-elementary ($kgeq 2$ or $ p+k geq 3$), the group $Grtimes_phi mathbb{Z}$ is relatively hyperbolic (relative to the mapping torus of each $G_i$). Then in Theorem 6.10 we prove the same result holds if $phi$ is atoroidal with central condition. We also prove in Theorem 7.21 that if all $G_i$ are abelian, the conjugacy problem is solvable for toral atoroidal automorphisms. These are analogue of the result of Brinkmann [7] (which gave the hyperbolicity result for free groups) and the result of Dahmani [12] (which solved the conjugacy problem of hyperbolic automorphisms).

We will extend the conjugacy problem of maximal toral subalgebras for Lie algebras of the form $\g{g} \otimes_k R$ by considering $R=k[t,t^{-1}]$ and $R=k[t,t^{-1},(t-1)^{-1}]$, where $k$ is an algebraically closed field of characteristic zero and $\g{g}$ is a direct limit Lie algebra. In the process, we study properties of infinite matrices with entries in a B\'zout domain and we also look at how our conjugacy results extend to universal central extensions of the suitable direct limit Lie algebras.

We will extend the conjugacy problem of maximal toral subalgebras for Lie algebras of the form $\g{g} \otimes_k R$ by considering $R=k[t,t^{-1}]$ and $R=k[t,t^{-1},(t-1)^{-1}]$, where $k$ is an algebraically closed field of characteristic zero and $\g{g}$ is a direct limit Lie algebra. In the process, we study properties of infinite matrices with entries in a B\'zout domain and we also look at how our conjugacy results extend to universal central extensions of the suitable direct limit Lie algebras.

Wir beschäftigen uns mit Problemen der algorithmischen Gruppentheorie und untersuchen dabei die Komplexität von komprimierten Versionen des Wortproblems und des Konjugationsproblems für endlich erzeugte Gruppen. Das Wortproblem fragt für eine feste, endlich erzeugte Gruppe ob ein gegebenes Wort über der Erzeugermenge das neutrale Element der Gruppe repräsentiert. Wir betrachten das gegebene Wort jedoch in einer komprimierten Form, als Straight-line Program (SLP) und untersuchen die Komplexität dieses Problems, das wir \'komprimiertes Wortproblem\' nennen. SLPs sind kontextfreie Grammatiken, die genau einen String erzeugen. Die Eingabegröße ist dabei stets die Größe des gegebenen SLPs. Eine Hauptmotivation ist dabei, dass für eine feste endlich erzeugte Gruppe das Wortproblem ihrer Automorphismengruppe durch eine Turingmaschine in Polynomialzeit auf das komprimierte Wortproblem der Gruppe selbst reduzierbar ist. Wir untersuchen das komprimierte Wortproblem für die verbreiteten Gruppenerweiterungen HNN-Erweiterungen (amalgamierte Produkte und Graphprodukte) und können zeigen, dass sich Instanzen des komprimierten Wortproblems von einer Turingmaschine in Polynomialzeit auf Instanzen des komprimierten Wortproblems der Basisgruppe (respektive Basisgruppen und Knotengruppen) reduzieren lassen. Weiterhin zeigen wir, dass das komprimierte Wortproblem für endlich erzeugte nilpotente Gruppen von einer Turingmaschine in Polynomialzeit entscheidbar ist. Wir betrachten außerdem eine komprimierte Variante des Konjugationsproblems. Das unkomprimierte Konjugationsproblem fragt für zwei gegebene Wörter über den Erzeugern einer festen endlich erzeugten Gruppe, ob sie in dieser Gruppe konjugiert sind. Beim komprimierten Konjugationsproblem besteht die Eingabe aus zwei SLPs und es wird gefragt, ob die beiden Wörter die von den SLPs erzeugt werden in der Gruppe konjugierte Elemente präsentieren. Wir konnten zeigen, dass sich das komprimierte Konjugationsproblem für Graphgruppen in Polynomialzeit entscheiden lässt. Weiterhin haben wir das Wortproblem der äußeren Automorphismengruppen von Graphprodukten endlich erzeugter Gruppen untersucht. Durch den engen Zusammenhang des komprimierten Konjugationsproblems einer Gruppe mit dem Wortproblem der äußeren Automorphismengruppe konnten wir zeigen, dass sich das Wortproblem der äußeren Automorphismengruppe eines Graphprodukts von endlich erzeugten Gruppen durch eine Turingmaschine in Polynomialzeit auf Instanzen von simultanen komprimierten Konjugationsproblemen der Knotengruppen und Instanzen von komprimierten Wortproblemen der Knotengruppen reduzieren lässt. Als Anwendung gelten obige Resultate auch für right-angled Coxetergruppen und Graphgruppen, da beide spezielle Graphprodukte sind. So folgt beispielsweise, dass das komprimierte Wortproblem einer right-angled Coxetergruppe in Polynomialzeit entscheidbar ist.

Wir beschäftigen uns mit Problemen der algorithmischen Gruppentheorie und untersuchen dabei die Komplexität von komprimierten Versionen des Wortproblems und des Konjugationsproblems für endlich erzeugte Gruppen. Das Wortproblem fragt für eine feste, endlich erzeugte Gruppe ob ein gegebenes Wort über der Erzeugermenge das neutrale Element der Gruppe repräsentiert. Wir betrachten das gegebene Wort jedoch in einer komprimierten Form, als Straight-line Program (SLP) und untersuchen die Komplexität dieses Problems, das wir \''komprimiertes Wortproblem\'' nennen. SLPs sind kontextfreie Grammatiken, die genau einen String erzeugen. Die Eingabegröße ist dabei stets die Größe des gegebenen SLPs. Eine Hauptmotivation ist dabei, dass für eine feste endlich erzeugte Gruppe das Wortproblem ihrer Automorphismengruppe durch eine Turingmaschine in Polynomialzeit auf das komprimierte Wortproblem der Gruppe selbst reduzierbar ist. Wir untersuchen das komprimierte Wortproblem für die verbreiteten Gruppenerweiterungen HNN-Erweiterungen (amalgamierte Produkte und Graphprodukte) und können zeigen, dass sich Instanzen des komprimierten Wortproblems von einer Turingmaschine in Polynomialzeit auf Instanzen des komprimierten Wortproblems der Basisgruppe (respektive Basisgruppen und Knotengruppen) reduzieren lassen. Weiterhin zeigen wir, dass das komprimierte Wortproblem für endlich erzeugte nilpotente Gruppen von einer Turingmaschine in Polynomialzeit entscheidbar ist. Wir betrachten außerdem eine komprimierte Variante des Konjugationsproblems. Das unkomprimierte Konjugationsproblem fragt für zwei gegebene Wörter über den Erzeugern einer festen endlich erzeugten Gruppe, ob sie in dieser Gruppe konjugiert sind. Beim komprimierten Konjugationsproblem besteht die Eingabe aus zwei SLPs und es wird gefragt, ob die beiden Wörter die von den SLPs erzeugt werden in der Gruppe konjugierte Elemente präsentieren. Wir konnten zeigen, dass sich das komprimierte Konjugationsproblem für Graphgruppen in Polynomialzeit entscheiden lässt. Weiterhin haben wir das Wortproblem der äußeren Automorphismengruppen von Graphprodukten endlich erzeugter Gruppen untersucht. Durch den engen Zusammenhang des komprimierten Konjugationsproblems einer Gruppe mit dem Wortproblem der äußeren Automorphismengruppe konnten wir zeigen, dass sich das Wortproblem der äußeren Automorphismengruppe eines Graphprodukts von endlich erzeugten Gruppen durch eine Turingmaschine in Polynomialzeit auf Instanzen von simultanen komprimierten Konjugationsproblemen der Knotengruppen und Instanzen von komprimierten Wortproblemen der Knotengruppen reduzieren lässt. Als Anwendung gelten obige Resultate auch für right-angled Coxetergruppen und Graphgruppen, da beide spezielle Graphprodukte sind. So folgt beispielsweise, dass das komprimierte Wortproblem einer right-angled Coxetergruppe in Polynomialzeit entscheidbar ist.