Seminar Geometric Group Theory -- Log-space conjugacy problem in Grigorchuk groups

11/11/2015 - 15:00
11/11/2015 - 16:00
Svetla Vassileva (Concordia University)
Burnside Hall, Rm. 920 (McGill University)

The definition of the Grigorchuk group is deceptively simple: it is generated by several actions on an infinite binary tree. However, it satisfies many uncommon properties: for example it has intermediate growth, but is not finitely presentable. In that light, it is interesting to see that many of the classical computational problems are ``easy'' in the Grigorchuk group. The word problem is known to be ``easy'' and we prove the same of the conjugacy problem. Here ``easy'' means log-space (and hence polynomial-time) decidable. We will introduce the Grigorchuk group and the precise notion of log-space decidability in some detail, following which we will discuss algorithms for the solution of the above-mentioned problems

Last edited by on Thu, 11/05/2015 - 16:26