## The compressed word problem in groupsAdd to your list(s) Download to your calendar using vCal - Derek Holt, Warwick
- Tuesday 26 November 2019, 16:00-17:00
- Watson Building, Lecture Room C.
If you have a question about this talk, please contact Chris Parker. Let G be a finitely generated group. The word problem WP(G) of G is the problem of deciding whether a given word w over the elements of some finite generating set and (their inverses) of G represents the identity element of G. It was proved in the 1950s that there are groups with unsolvable word problem, but for groups with solvable word problem, it is interesting both in theory and in practice to study the time and space complexity of WP(G) as a function of the length of the input word w. Many of the groups that arise in geometric group theory, including nilpotent groups, hyperbolic groups, Coxeter groups, Artin groups, braid groups, and mapping class groups are known to have word problem solvable in low degree polynomial time (usually linear or quadratic). For the compressed word problem CWP , words are input in compressed form as straight line programs or, equivalently, as context-free grammars. For some words, such as powers of generators, the uncompressed word can be exponentially longer than its compressed version. So the complexity of CWP could conceivably be exponentially greater than WP(G). As motivation for studying this question, we observe that it is can be shown that the ordinary word problem in finitely generated subgroups of Aut(G) is polynomial time reducible to CWP . It turns out that for some classes of (finitely generated) groups in which WP(G) is solvable in polynomial time, including nilpotent groups, Coxeter groups, and right-angled Artin groups, CWP is also solvable in polynomial time, whereas for others, such as the wreath product of a nonabelian finite group by an infinite cyclic group, CWP has been proved to be NP-hard. In this talk, we will discuss a (fairly) recent result of Lohrey and Schleimer that, for hyperbolic groups G, CWP is solvable in polynomial time, and speculate on whether this result can be extended to include groups that are hyperbolic relative to a collection of abelian subgroups. This talk is part of the Algebra Seminar series. ## This talk is included in these lists:Note that ex-directory lists are not shown. |
## Other listsPostgraduate Seminars in the School of Computer Science Analysis Reading Seminar 2019/2020 Human Computer Interaction seminars## Other talksFENL: an ISE to mitigate analogue micro-architectural leakage An attack on ECDSA using lattice techniques School Seminar The Large Mathieu Groups Privileged side-channel attacks for enclave adversaries The galaxy-halo connection in the cosmic web |